I know some effects like the famous Klon Centaur run charge pumps for more output, and/or headroom like you mentioned, but some effects require more or less voltage just for the chip to operate within accepted parameters. Like the Robot from Death by Audio, requires around 3.5 volts for the HT8550 to operate correctly, and then the Echo Dream, runs best around 15 volts for the LFO chip to operate and not tick. I have a variable voltage controller I built and I've run most of my pedals from 8-15 volts, most of them have no really noticeable changes. I build a Ruby amp with a 386-3 which can handle like 20V or something, and yeah it's way louder with 15 Volts.
I only order 25V or higher Electrolytics now for this reason!
As far as regulated DC power supplies, you're not guaranteed they are going to be well filtered, and I'd recommend building a little regulated power supply yourself with a 7812 or higher and some filter caps like the "huminator" design that's out there. You could also run your 12V supply into a huminator style design to clean it up if it's noisy. You can get a LM317 regulator kit with filtration for like $5 off ebay and build it into a nice little box for a regulated power supply that's pretty flexible with a digital readout.
I'm not by any means a pro on this, but as long as your components are rated for the voltage you'll be ok. 9V seems to be a vestige of available battery technology, and like I said most things work just fine at higher voltage. When I built my Robot pedal I used some diodes from the power leg to get down to 3V to the HT8550, so if I run the pedal off anything other than 9V, that chip will be seeing more voltage and it either doesnt work at all, or sounds crappy. In place of that you can run regulators to get a more flexible design for varied input voltage. Just make sure you check out the chips and transistors data sheets before you go and fry a relatively expensive part!
-Brett