Supposedly strongholds only spawn between 640 and 1152 blocks from the origin and there are only three per world. On the SMP server I play on, all that land has been explored for a very long time, so it obviously won't be regenerated unless somehow deleted. Does this mean that the strongholds will never spawn? Can they be generated in new chunks that are further out if they don't exist yet?
All chunks generated before 1.8 will use the old world generation algorithm. They will never contain strongholds unless they are deleted and regenerated.
If you wish to find them, I'd recommend going to a 1.8+ chunk (there will be a visible line where the generation changed) and use an Eye of Ender.
EDIT: It seems that 1.0.0 has not in fact implemented the increased spawning that was promised. Silly Mojang! However, the rest of the post still holds.
Anecdotal answer: We have a stronghold discovered in a world that was started in Alpha. It was in previously unexplored territory. We had to go to a part of the world explored in 1.8 & use the eye of Ender to find it.
(Thankfully the end portal was intact.)