I'd try running them direct drive first, with the settings I mentioned above, and playing with the acceleration.
Another thing that may make a large difference is adding a damper. If you're seeing resonance, a damper can sometimes double performance. See this thread for more info.
http://www.cnczone.com/forums/stepper_motors_drives/32284-my_take_stepper_damper.htmlGecko G201x's are about $125 each. Then add the cost of a 72V power supply.