It's very simple, but I'm trying with simple code to get where I need to.
Basically what happens is that the motor generally starts turning rightly, but it is not reliable because it may reverts its direction and turn in the other direction in a sudden, or starts oscillating around a point making the tracking of its position impossible because the counter displays a position but it doesn't actually move that much; I debugged the current position via Serial.println(stepper.currentPosition) and a visible coloured marker upon he shaft.
I really don't know what's the problem. I'm using a new NEMA 11, and a new 9V battery, but I had the same problem also with a NEMA 17.
If you mean a PP3 style 9v battery then that is totally unsuitable for a motor, and stepper motors are especially hard on batteries. Try a pack of 6 (or 8 ) x AA cells or a mains derived power supply.
What happens with a much lower stepper motor speed?
Just look at the service hours graph. See the line for 250ma. Not much time. Your stepper motor uses much more current that that, so NONE of those type batteries will work for you.
I tried using a power supply but the result doesn't change a lot, it rather worsened.
By using the supply the motor didn't even move, it was trembling, and I was sure that it was taking the arduino signal and the power supply, but the shaft didn't rotate. So I tried manipulating the screw in the a4988 and the shaft started moving randomly. I was able to find though, a point were the shaft could rotate almost normally but it still froze for few moments every turn.
The motor and the driver are new, I'm using them for the first time now. I used the arduino for few weeks last summer, but it is almost new as well. I've no idea how to debug the hardware to check where lies the problem, since it is obviously not a software fault.