severe scalability issue with adding users

My team is integrating xwiki into a heavily trafficed commercial site (over a million uniques a day). We have hundreds of thousands of registered users. Our current tests indicate that the tie to add a new user is linear with respect to the number of users already added. We went from less than 1/2 second per user to over a second per new user as our test data grew from 3k to 10k users. The bottleneck seems to be a database query that has to iterate over all existing users in order to add an additional user. Any feedback would be appreciated. As far as I can see, we are using standard xwiki functions to add users. Let me know what information you need from me in order to help provide accurate feedback. Thank you, Andy