Sandbox User Code Service and low performance

Do you have insight into the limits they setup for the code? they may have set it so high they just have bad code monopolizing the service. That's the first place I would look. For testing, I would block all their solutions than try to run yours.

I would profile the service itself and see the resources it is consuming on average and the peaks, you could use native perf counters or PStools Process Monitor.

Also check the conifiguration of the service itself (courtesy of MS http://technet.microsoft.com/en-us/library/hh230318.aspx):

#Recycle the UserCode Service
$server = [Microsoft.Sharepoint.Administration.SPServer]::local

$userCodeServiceInstance
$getChildMethod
$type = $server.GetType()

foreach($method in $type.GetMethods())
{
     if( $method.Name -eq "GetChild")
     {
          $getChildMethod = $method
     }
}

$genericMethod = $getChildMethod.MakeGenericMethod([microsoft.sharepoint.administration.spusercodeserviceinstance])
$userCodeServiceInstance = $genericMethod.Invoke($server, $null)
$userCodeServiceInstance.Provision()

You can tweak these if there hardware will support larger values (depend on normal load). If they already have this configured to far above the defaults, it could also be causing problems if the machines can't handle it (hence neededing to profile it above)

Additonally, if they are running it on the APP server only, you may want to consider running it to the two web serving VM's as well to laod balance the service.

Becouse these are VM's you will want to look at the host utilizations as well, if the CPU / Memory is over subscribed this could be causing locking issues on the host, and thus your processes are taking longer as they are waiting for the CPU request to process.