Those ‘old’ slugs are kept in the postmeta table. Using phpMyadmin you could delete them ALL with:
DELETE FROM wp_postmeta WHERE meta_key = '_wp_old_slug';
Or delete them individually in that table.
Backup your database before attempting.
There is no file called register.php rather it is an extension of the wp-login.php page. The function to call/display the register link on your page is named wp_register(). If you are getting a 404 Error as opposed to a PHP error, I would confirm that /wp-login.php exists firstly!
Also, are you using a certain theme or a widget to allow users to register?
