When you run in the sandbox are you running the tests in parallel? When you deploy to production the tests are not run in parallel, so it will likely take longer to run all of them. If you are running in parallel in the sandbox, you can switch to not run in parallel to get a better idea of how long the actual deployment will take.
If you are running in parallel in the sandbox it could be that there is some contention occurring for a shared resource. Also, Apex tests are placed in the Apex Job Queue for execution according to the documentation, so there could be some delay there, although 6 minutes+ seems excessive.
There could be different causes for the fluctuations in overall time between entire test runs. The documentation on Salesforce Asynchronous Processing has more info on how asynchronous processing is handled. It could be that there are a differing number of other orgs running at the same time (less when it takes less time...more when it takes longer). It could be that some tests depend on some shared resource and during certain test runs they happen to execute at the same time and in other test executions they run at separate times and don't have an issue.
I would rather have longer deploys and more unit tests that cover as many use cases as possible. I would not recommend that you remove valid tests (e.g., negative tests, edge cases, etc.) to reduce running time even if doing so saves time and doesn't reduce coverage. The 30 minutes you save on your scheduled deployments will easily be eaten up by time lost due to regressions introduced that would've been caught by the removed tests.
For what it's worth, I've deployed to an org that has roughly ~1000 test cases (methods) and a relatively complex data model and it takes close to 45 minutes for production deployments.
One approach that you can take to save some time is to run the validate only deploy the night before the deploy (assuming you deploy in the early morning -- adjust this example as necessary) and then on the following morning of the deploy run the deploy without the validate step. Salesforce will still do the validate and the deployment will fail if it doesn't validate, so you don't have anything to worry about. If you are currently doing the 1.5 hr validate deploy followed by a 1.5 hr actual deploy this will save you 1.5 hrs on the day of your actual deployment.
Lastly, if you are completely stuck you could start violating some testing best practices:
- Unbulkify tests. Always create the minimal amount of records for a test.
- Remove methods that don't add additional coverage.
- Use existing records in the database.
If you do any of them it would be a good idea to structure the test code in a way that you could "toggle" that functionality. E.g., have a setting that holds the number of records to create for bulk testing and in preparation test it with the high number and on the actual deploy set it to 1, use a custom setting to conditionally execute tests that don't add coverage and don't execute them on deploy, etc.
Best Answer
A (partial) list of things that have buggered our tests on deploy (it boils down to: does your deployment include absolutely everything your Apex code needs?):