you can't get a solenoid for basic stamp, unless someone ever thought of creating such a specialised application.
solenoids are usually power device, that can hold their pin with quite some force. I doubt you will easily find low power ones (such as 40mA, but you still need way lower than that, about half, with logic consumption).
what you need to do is make a simple driver for a solenoid, using a transistor for example. a pin from the basic stamp controls the transistors gate, and you put the solenoid in series with power - transistor sink or transistor source - ground. This way, current would rush through it whenever the transistor is open. You will need to have a separate power for the solenoid and grounds connected in common.