Cheap and simple step-up converter
Olin's right about Microchip doing some nice switching regulators - I use the MCP1603 parts quite regularly. However these are buck regulators and don't have a 5V fixed option anyway. I just had a quick look on Farnell and didn't notice any MC parts that fit for this requirement. It may be worth a look on their website though.     

The cheapest 5V boost regulator I am aware of that can work down below 1.8V at 500mA is the NCP1450 from ON Semi. It's £0.63 in qty 1, can source up to 1A, and can startup with low as 0.8V with no load. It comes in a nice and small 5-pin SOT-25 type package.
I haven't used it, but I saved it whilst searching for another regulator as it looked like a nice part. ON Semi make a lot of decent cheap parts in this category.