Sadly you wouldn't find that perfect temperature sensor having all you need. I think LM 35 is the IC that you need. It has a supply requirement of 4v - 30v which covers the range you've specified. It also has high accuracy of 0.5V. So why not LM 35?
I'm going to go out on a limb and answer for the OP. His problem is logistical rather than technical. They are pure unobtanium wherever in the world he is located or at least it's his impression that they are.
Sorry, my reply was for thermocouples and RTD devices with which I have had some experience. I took the OP's word for it that the LM35 did not meet his requirements. If he had made his REQUIREMENTS CLEAR we could have saved some bandwidth and disk space on this so far utterly useless thread. I've never used an LM35, but it sounds like a useful part to have in your bag of tricks.
Be sure to use the right circuit to achieve such values. Heres an example from my experiments with the device;
**broken link removed**
Disregard the signal generator, it was for simulation of the circuit, but as you can see, its not as simple as connecting it and measuring 10mV increaments for its full -55 to +150 range
I'm using the same technique with a 16F877 it works fine.
The only trouble I found was with the +5V to the LM35, with the two diodes in the ground line.
The LM35 is rated at +4V thru 20V. With a fwd voltage drop of about 1.4V across the diodes, it gives only +3.6V across the LM35 and I found at the higher temp end the linearity fell off.
Finished up using the +9V supply on my pcb, cured the problem.