Some of my favorite surplus dealers have deals on solenoids:
Alltronics,
All Electronics,
BG Micro, and
Electronic Goldmine.
I bought some of the ones from BG Micro, and a few of each of these, to try out for a project I'm working on:
tiny one with return spring, and
larger one with loose armature. So, if you want to know more about any of them, feel free to ask.
I've got a few extras, so if all you need is solenoids, and can't find other goodies from the surplus dealers to fill out a minimum order, drop me an email, and I can sell you a couple of mine.
Ran