I know you're not willing to disable 3rd party plugins on your production site, but maybe you can create a test installation and try to register the same amount of users and we'll check whether such problem exists on default installation of yours without any 3rd party plugins.