I think I've seen something like this in a load cell resistive bridge. Though in my case I took great pains to make the supply voltage as close to a steady 5.0 Volts as possible. Allowing the supply voltage to fluctuate makes the instrument amp and the analog-digital conversion more difficult to accomplish.
Would you be able to install a high-accuracy voltage regulator in the sensor, that allows it to accept input voltages up to 20V, while regulating the voltage across the sensor's element a constant 5V? It would look a little like the attachment below...
As for the other separate requirement, it took me a while to tease the two of them apart, given how they are related to one another. Does the sensor have to be referenced to the same ground as the supply voltage? Could you create a false ground for the purpose of this sensor? The reason I ask is that the upper and lower limits you stated for output (0.5v and 4.5v) aren't starting out a 25% and 75% of the 5V base supply. So the slope of the Y=Mx+B lines going from the supply voltage's 25% and 75% ratios aren't going to be the same, so you add a lot of complexity. Maybe you can fool the sensor by making it think that ground is some other voltage, causing the output to be the sum of the "high ground" voltage plus the lower scale sensor output voltage. And you choose that to equal 25% of the supply voltage.
Then all you need for the scaling with respect to the upper limit of the supply voltage is a resistive voltage divider with points at 25% and 75% to pick from. I think I'm over my head now, but maybe you can see the other side of the river from here.
STF