There's a difference between how many records a database can hold and how many users need to access the system simultaneously on a regular basis. For the latter it's a much harder question because it depends not just on hardware but usage patterns and where the users are located (network latency), and I mention that specifically because you mention Captive BPO, which suggests your users might not even be on the same continent as the hosting. (I'm not really sure why you mention it - is there something specific about the intended provider that makes you think it will be a problem?) So it's not so much a CiviCRM question as what type of hosting setup you're going to have. CiviCRM can function in a load-balancing environment, if you have a crazy large number of actual simultaneous users.
For the former it depends what you're doing. If you try do something regularly that processes all 5 million records, you'll probably run out of RAM. If you're just loading a single contact record page it will handle it fine.