Allow users to change their names. Their old username URL points to their new username URL for, say, 30 days. Include a notice on the top of the page when this redirection takes place, a big yellow banner with red text right below the top header stating "This URL will soon change to whatever.newgrounds.com, please make a note!"
After 30 days, the old link goes dead and the name is freed up.
The only problem I can see with this is people would start "blocking" usernames and it would create a huge headache for you to admin this new system. Permanent lockdown of names would also prove a problem liek this as well.
You could keep a database of all the users of a certain name at one point or another, and when a link is followed the banner could pop up again and say "Not who you're looking for? Check the registry". Apon clicking, they could be given a link table allowing for redirection to any of the former users of the name.
But that might be a little over the top...or maybe not:
The best idea I can think of is a slight take on the way MySpace does it: Allow the DNS names to be changed at will, but the name just re-directs you to the account numbered page. DNS is useless for websites doing the linking, as anyone writing a web page with a link can easily be bothered to copy and paste the numbered link into their HTML code. Hell, that's just as easy as copy-and-pasting the DNS-prefixed URL. The whole purpose of a DNS name is for people to remember easily, so the sole purpose of that could be for users typing a URL into their browsers off the top of their head. Combine this with the DNS-prefix name history feature and you might just have yourself a workng dynamic system.