Juan,
There are a couple of maximum speeds to consider:
1) The maximum speed of step pulses that your microcontroller can generate. With AccelStepper on a normal (AVR) Arduino, this is about 4000 steps/second.
2) The maximum speed that your motor driver can properly generate the step waveform. For drivers like the Easy Driver and Big Easy Driver, this is very high - like probably 100K microsteps/s.
3) The maximum speed that your motor can spin with no load (i.e, nothing connected to the shaft). This varies widely, and depends on motor type, coil resistance, impedance, driving voltage, and type of driver circuit. Typical values for small NEMA 12 or 17 motors are usually between 5 and 20 Revolutions/second.
4) The maximum speed that your motor can spin with the maximum load your system will be applying to the shaft. This of course is completely dependent on your mechanical system.
The maximum speed you can get out of your system will be limited to the slowest of these four things. For most people, #4 is the lowest, and thus most limiting factor. #1 is the second most common limit.
Switching to full steps rather than microsteps can allow you to run your motor faster (this is done on Easy Driver and Big Easy Driver by tying MS1, MS2, and MS3 low). Using a higher input voltage to the driver can increase torque, and thus high end motor speed before it poops out. Using smooth acceleration rather than jumping between speeds can also help reach higher speeds (this is where Accelstepper really shines).
If #1 ends up being a problem, you can move to faster Arduino compatible boards. If #3 is the limit, then you can go to bigger/better motors. If #4 is the limit, then working on decreasing the mechanical load is the solution to running faster.
Hope this helps-
*Brian