Allowing username changes, and google penalties

The problem I see is, if member's url is http://www.mydomain.com/user, and they are able to change their username, google will no longer find http://www.mydomain.com/user, because the user's profile is now at http://www.mydomain.com/newusername.

After a few hundred of thousand of these, google could penalize a site for so many 404's. My question is this:

Would it be possible to have the links to the members profiles throughout the site point to http://www.mydomain.com/userid , but leave their username as the anchor text that links to their profile? Basically, I'd like to allow my members to change their usernames, without their profile url changing too.

that is a good point, and fact of the matter is when the profile is cached, its cached under the USERID, not the username.

Disabling permalinks for profiles should do the trick.

What percentage of your members change their usernames? With my sites it is not too many.  If you have "a few hundred thousand people changing their user names", you probably have more problems than Google having to reindex your site more often - and more opportunities also.

Is there an option to disable profile permalinks?

Administration > Settings > Permalinks.

If you disable permalinks, your search engine ranking may come down.

I tried disabling profile permalinks, when I mouse over people's profile links, some show the ID, some show the username, totally useless feature I guess.