Grundsätzlich gilt bei Schrittmotoren je höher die Spannung desto besser ist es. Der Schrittmotor sollte mit einem konstanten Strom angesteuert werden. Der Schrittmotortreiber muss das aber können. Du könntest einmal versuchen mit den ca. 12V zu arbeiten (nur kurzzeitig zum Testen) ob es dann besser wird.
Welchen Treiber verwendest du? Hast du den L297/L298 genommen oder etwas anderes?

MfG Hannes