Could it possibly be that the stores had just sold out? 

There's no new version coming out until probably 2005, and MS would be insane to stop producing the program, since FS is the most popular game of all time.

Living close to NYC myself, I'm curious how long it took you to go to ALL the stores in the NYC area.  That's a lot of stores.  My guess is you went to a few and they didn't have it.

Finally, regarding them pulling an old version when a new version is released....go to any Wal Mart right now and look for FS98.  You'll see it sitting there plain as day.  This, despite the fact that six years later FS9 was released.