SourceSafe is licensed per user. If you have 5 developers, you need 5 licenses (regardless of the # of machines or simultaneous connections). It should work fine on a team that size.
Teams of up to 5 people can also use TFS Workgroup Edition, which comes 'free' with MSDN Premium.
VSS 2005 does support VS 2003, yes.