delay at logon while applying your personal settings

Our application is creating a new Windows user in answer to each request. In space of one year hundred of thousands of new users are being added and subsequently deleted. We noticed that after a while our servers start to slow down while logging on a new user. The delay occurs when Windows displays "Applying your personal setting" message, taking 25 seconds on a used server as opposed to 5 seconds it takes on a brand new machine. Each time a user logs on it logs on using a brand new user account. We cleaned up the registry of any residual entries left over while adding and deleting a users but it made no difference. Is there any way to correct this problem without having to reinstall the OS?