Is it possible to have a little button next to the username in your Membership Request Web-Part called "Check Availability"? when clicked it will query the FBA store to see if it is taken before the new credentials are registered?
Like the way you can do when you register with Live ID, MSN / Hotmail etc. to see if your preferred email is available?