have used one that can do 2A 12v and it works well with 8 servos (with voltage regulator obviously. And if you make your own regulator circuit, definitely don't connect the power wires of the servos to the 12v supply instead of the regulator output. Erm... not like I've ever done that... )
Depending on the regulator you are using, you could well be wasting a lot of power as heat in the regulator. Most regulators have a certain "turn on" voltage; you want to try to stay as close to that as possible with your power supply. For instance the 7805 is around 7 volts; using a 12V supply with that, that extra drop of voltage goes somewhere, out the regulator as heat. Using a 9 volt supply would be better.
Also - if you are running servos, its best to use a 6 volt regulator; most servos are designed to run at a peak voltage of 6 volts to get the most torque and performance from them.
Finally - regarding using the Arduino alone to control 12 servos: Yes, this can be done, and I believe with the built-in servo library (I don't think there are any limitations with this library). The only issue is that as you add servos and other code to your system, you may run into timing issues that can cause the servos to "jitter"; periodically, or sporadically (it depends on what is going on in the code, as well as the power supply and the servos themselves). Generally, when controlling a large number of servos, it is better to use a servo controller device, which generally takes the form of a dedicated microcontroller hooked up using a serial control system. Generally, you can use the software serial library to control these boards (so only one or two i/o lines used, instead of one per servo), and the microcontroller on that board, once you pass it the commands, keeps the servos constantly updated to keep them in place - effectively off-loading the processing off the Arduino. They aren't very expensive, and they can generally be daisy-chained for more servos if needed (each board is addressable in some manner determined by the manufacturer).
I tend to favor Pololu's offerings, but there are other manufacturers as well. Generally, as I said, these boards are controlled by a built-in microcontroller that is programmed to read serial commands and control servos, nothing else. In fact, it wouldn't be too difficult to make an ATMega328-based servo controller, if you wanted to. There probably exists such a product already. However, most are controlled by PIC processors, from what I have seen.