I'm targeting frequencies of around 25 to 30 Hz (which roughly translates to a switching on/off signal every .04 to .03 seconds).
The Arduino can perform 16 millions instructions per second. 0.04 seconds is an eternity. Direct port manipulation, rather than digitalWrite(), can cut down the time needed to switch a pin even more.
The real limiting factor appears to be your hardware. How fast can the solenoid valve react?
How are you powering the solenoid valve? What is the Arduino actually controlling? A transistor, I hope.