I'm going to put into my own words what you wrote: You have a 24V solenoid that is rated at 1A, full draw. You will be running it at 12V, which you assure us will still work with the relay because of what you've read other people saying. This means it will "pull in" at 12V, which implies it will do that with about half an amp. Unless it is one of those relays that can be cross-wired for either 12V or 24V operation. In which case, the current required at 12V might be doubled to 2A. You don't state the relay, don't provide a web link to it, and therefore there is no way anyone can cross-check these details. We just have to make broad assumptions. In this case, I have to assume that it could be as bad as 2A @ 12V, though it could be as little as ½A for all I know.
This variation of 4 is right at the point where BJTs go from cheap to expensive. A PN2222A can possibly (maybe) handle ½A. (Same with 2N3904.) If you drive it so that the Vce is low, perhaps 0.3V or so, then you might be talking about a fifth or a sixth of a watt, which it can dissipate. But if this is really 2A, then that's not the right part. And you go from "easy to get" to "less easy, and more expensive." Plus, probably, some heat sinking as well if you plan to run this continuously -- which is another thing you don't state.
As far as it goes for the BASIC Stamp, as you surmise there is a total port dissipation limit as well as a per-port pin limit. And anywhere near those limits, you cannot expect the output of the pin to be either 0V or 5V. These are MOSFET outputs and they aren't that big -- they will be severely loaded down, which means there will be a voltage drop across them. This means the design, if it plans on using 20mA or more, must take into account these drops as well as everything else. It's much better to design for much less. You should expect to supply no more than about 5mA, maybe 8mA, though I'd want to keep it lower than higher, if possible.
So. What to do? You can use a MOSFET, instead of a BJT. The nice thing there is that the MOSFET outputs will play nicely with the MOSFET driving the relay. The bad side is that they cost more. If you are cheap as I am (I like to pay less than a penny for a BJT), then they are on the order of 50 to 100 times more expensive and I say "to heck with that." But if you don't mind paying a dollar or two, then perhaps a MOSFET would be good. You need to make sure their gate threshold voltage is compatible with your 5V rail voltages (if you find one with too low of a gate threshold then the 5V might puncture the oxide and destroy it, though I doubt you will run into that problem.) Otherwise you need to select an NPN BJT that can support the higher currents implied.
I'm going to hold short of getting into more detail until I understand better about the relay you are using. There are other issues, such as the use of a snubber or free-wheeling diode to deal with inductive issues in the relay when switched off. But until I know more about the relay, a specific design should be held back, I think. The possible range of details are too large a span, right now.
What I'd be looking for is the avoidance of boutique parts and the use of standard, well-worn path parts that have proven themselves to be generally available at decent prices from a variety of suppliers. By the way, the web has hundreds if not thousands of web pages on driving relays from microcontrollers. You might be able to find a specific design for the relay you actually have and at the voltage you are supplying.
Another detail that would be nice to know is this: You have a 12V battery. You don't say how the BASIC Stamp is supplied with 5V. I know they all have a 5V regulator on board and that this regulator can handle "up to 12V" at its input. But if you are using a car for this, then you have yet another problem to deal with that you haven't talked about here. Car systems are notorious -- they have huge spikes which almost need to be treated like lightening strikes (more than 100V) and the normal operation is NOT 12V or less, but higher. So that would almost certainly exceed the specs on the BASIC Stamp, if you are doing that. So more details here, too, please.