Are you using Community or Enterprise ?
How is your WCM structured (eg. 1 web project with 1 webapp, or 1 web project with X webapps, or Y web projects with on average Z webapps each or …) ?
Do you use the virtualization server or not ?
Have you considered upgrading to the latest release which may give you a performance boost (eg. Enterprise 3.3.3 or Community 3.4b, at time of writing) ?
If the user sandboxes have no modified items (or the modified items can be thrown away) then you can simple uninvite the user (and delete the sandbox). If you wish to reinstate the sandbox at a later date then you can simply re-invite the user to the web project.
Regards,
Jan