I think that's right. I got my first modem in 1985 and been on the Internet since the start of the 90s. I never re-use user names between sites, frequently delete my accounts and start with fresh ones.
I've started recently using random word generators to generate common words to use as usernames.
Whenever I want a username that isn't associated with any internet persona of mine, I look around on big forums for names and start googling them. I think the best is to find one that's a character in some obscure book/story, and then pick another character from that story - thank Wikipedia for having this type of info for all sorts of things. Best is something odd enough that it isn't likely to be taken already, but still common enough that the search results for it are too noisy to see a few forum posts.
But then, it depends a lot on what you're trying to hide, and who you're trying to hide it from. Keeping bored teenagers on 4chan from finding your home address and keeping whole departments of the FBI from tracking you down are whole different ballgames.
Actually, part of me would like that to catch on for pseudo-anon usernames, so I'm not quite as trackable between accounts.
Ideally I guess I'd come up with a few dozen random name systems, and hop between them for each account... such a hassle.
I guess you want to pick names that have lots of false positives when searching. But of course you can't ping google to check. Is there a known mechanism for this? I guess the old dice + newspaper to pick a phrase?
Maybe I'm too sensitive about this since nobody in the history of the known universe has the same name that my parents picked, so any hits in search engines are never about anyone else. Unique usernames function the same way.