Weirdly, Facebook or Google have so many users that this isn't much of a problem for them.
Whoever picked a really desirable username (e.g. "Frank") probably already did so back in 2008. The many, many users who now come and want to try it, never to come back, will probably have to be content with "Frank32183" instead, and once you accept that, there is no particular reason why you wouldn't accept "Frank32184" just as well (not everyone can be so lucky to have a unique name, like me!).
Another factor is that, famously, big data companies never remove user data unless both public opinion and a court/law really, really urgently tell them to, because their user data is their business model. Being able to say "we have 3,000,000,000 users" is more important than ensuring that they are all live users, because it attracts more new users, plays better with advertising customers, etc. Keeping users happy is important to the company, but not quite as important as keeping them in the first place.
In a smaller, more familiar network the trade-offs may be different. Indeed, actually removing your data without a trace might be a valuable unique selling point of an exclusive online platform. But the really big companies who aim to have everyone on the planet as their customer simply don't operate in that space.