Vector based painting software, with an infinite canvas. Seriously, watch this video. You will be amazed. The start is quite impressive, but wait till she zooms into a painting of the world, that continues going into landscapes, and then into someone's eye.. Just, look.
Also what's amazing is, you can open the Software, paint away with no care for what size or resolution or anything you are painting at. There's no need to be bogged down by such limitations, or have to think ahead about how big you want this piece to be in the end etc. Sometimes you just want to paint without knowing the outcome. When you've done something that you like, you can specify the DPI, the Resolution and all sorts of other things. This. is. amazing. Really, I don't need to say how awesome that is. Just watch, and download the trial (I'm raving about it but I've not even opened the trial yet!)
On second thought, I'm not sure so much freedom is a good thing to me. This comment to the talented Serge Birault rung true : "Considering that you can zoom infinitely, aren't you afraid to fall into a time/space warp while painting hair as obsessively as you do? You might never be able to leave the canvas again... ;D"