Cualquiera de 5 a 9 voltios, (12 no lo vuelvo a usar

) el regulador es muy malo), y prevee mas de 16mA (mu facil) que es lo que consume el arduino duemilanove en arranque, luego se queda en unos 15mA reales, luego suma lo que le añadas en consumo.
Hoy en día hay muchos cargadores de casi todo a 5V, cualquiera de ellos te sirve según el proyecto por supuesto por los consumos, arduino o mejor dicho el atmega328 o similares trabajan perfectamente un poco por debajo de esos 5V o sea se, que si tienes caída de tensión por consumos, funcionará perfectamente en la mayoría de los casos.
Saludos