As you say, 5V seems too much - there's a burnout-about-to-happen smell once it's run for a bit and it gets too hot to touch pretty quickly.
Anyway I just accidentally put 12V through and that burnt it out pretty quickly. Time to get the soldering iron out for motor #2 of my 10 
From reading around a bit more [ World’s Smallest Stepper Motor with Arduino and EasyDriver - Electronics Blog ] one way to go seems to be putting the EasyDriver power input on the 3.3V regulated level - make sense given what I've seen so far so I will try that (together with keeping EasyDriver current at the lowest 150mA level by adjsuting the trimpot).
Will be interesting to see how much torque I can get. I have a plan to have lots of small objects moving so having a stepper at a price point < 1 GBP is potentially very handy.