I order some steppers from CNC4You on eBay on Friday, and they turned up today with DPD (actually it was early: DPD text you a 1 hour time slot in the morning. The guy turned up a minute before the earliest time allowed and we had to stand their awkwardly making small talk until his scanner would let me sign for the package :'D ).
I don't have the proper drivers yet, but I was desperate to check that they worked and see what they were like. I hooked them up to an EasyDriver board and turned the current pot up to the heady max of 750mA. Coupled with the world's simplest Arduino stepper sketch, I had working motors!
I'm really impressed with these so far. They weigh just under 1.5kg each, and even being driven with 750mA @12V they produce useful torque. I was totally unable to stall them by hand. This looks quite promising for my machine!