Re: SourceSafe
VSS was essentially a file-based solution that worked through shares - and that was one of its main weaknesses. It was also quite unusable and unreliable over slow connections for that reason.
It required a quite careful maintenance, avoiding large repositories, and a quite reliable network to minimize issues.
TFS is database-based, and works through HTTP. I wouldn't be surprised if they re-cycled part of the VSS code, though.
Not that CVS was that astounding piece of code, back then, and didn't have its own issues. CVSNT was slightly better, but it was essentially a one-man product and delivered its shares of trouble as well.
More expensive solutions like Perforce were better, but far less available, especially in small companies and small teams.
Anyway, back in those days even VSS or CVS (SVN would have been available only in 2004) were far better than *no VCS at all* - I saw more than one team just making copies of files to some server shares - the worst situation I encountered was when the shares were on the department manager PC, on a single disk, with no redundancy at all....