Your MSC (roughly the thing that people in your geographic area connect to) would talk to your HLR (the place where your records are stored specifically, regardless of current location) to authenticate you and make sure you're a real subscriber, but it wouldn't necessarily do so before every single call. At the end of some billing period, the operator whose services you've used (MSC owner) would send billing records (using the TAP format) to your operator, usually via FTP or similar, and your operator would use them to send you a bill.
This worked for post-paid, when customers were assumed to be trusted, and legal sanctions could be levied against those who refused to pay their bill. However, this approach broke down when prepaid plans were introduced. This led to the invention of CAMEL, which is basically a realtime protocol which lets the MSC ask the HLR whether a given call was permitted or not.
And since the cloud providers don't have the problem in your first sentence (even if the customers pre-paid, they're still easily identifiable), they never bothered to implement the solution from your last sentence. But seriously, the problem of accurate, real-time billing is not a new one, and it's been solved before several times already (e.g. RADIUS/Diameter of dial-up ISPs).