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.
Also, chunks from 1.8.x have a much lower stronghold-spawning rate, so even if 1.9+ generation will spawn a stronghold there, the 1.8 chunks will be devoid of them. However, newly generated chunks will contain strongholds, so all is not lost.
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.