Hello, Rob
There is a Username Blacklist extension available for MediaWiki 1.5.8 and above, which can be downloaded from http://svn.wikimedia.org/viewvc/mediawiki/trunk/extensions/UsernameBlacklist. See http://meta.wikimedia.org/wiki/Username_Blacklist for more details.
I've set up the extension to my MediaWiki-1.6.3 site. It seems to work well!! Thank you for your information.