Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?
Yes!

A bit convoluted example is the following:

Suppose you have $n+1$ nodes and you run djikstra from $a_{0}$
Let $A=[a_{0},a_{1},a_{2}.....,a_{n}]$ the final result of the algorithm(i.e the nodes of the graph sorted by their distance from $a_{0}$)

We will now create a graph which will require every edge to be updated:

First of all add edge $e_{i}=(a_{i} , a_{i+1})  $   with $cost(e_{i})=0$ for every $i&lt;n$

Let $M$ be a really Big Value. 

For every $i&lt;n$ and $j&gt;i+1$ add the edge $e_{ij}=(a_{i},a_{j})$ with $cost(e_{ij})=M-i$

At every step $i$ of the algorithm ALL values of the nodes will be updated.

ex.  $M=100,  n+1=5$

Distance matrix for $A$

step 0: [-,0,100,100,100,100]

step 1: [-,-,0 , 99, 99 ,99]
and so on....