We had logic that was calling Install-SPSolution twice on different solutions (same behavior observed with stsadm), and then logic for waiting for the deployment to complete. In rare instances, what happened, is that both solutions were attempting to acquire the deployment lock before either thread got the lock; one thread would succeed and one would fail with the Primary Key exception.
So the log would look like:
Solution Deployment : Acquiring deployment job lock for server ... solutionA.wsp
Solution Deployment : Acquiring deployment job lock for server ... solutionB.wsp
Solution Deployment : Successfull ACQUIRED deployment job lock for server ... solutionA.wsp
System.Data.SqlClient.SqlException: Violation of PRIMARY KEY constraint 'PK_Classes'. Cannot insert duplicate key in object 'dbo.Classes'.
Instead of:
Solution Deployment : Acquiring deployment job lock for server ... solutionA.wsp
Solution Deployment : Successfull ACQUIRED deployment job lock for server ... solutionA.wsp
Solution Deployment : Acquiring deployment job lock for server ... solutionB.wsp
(followed by solutionB being denied and waiting for solutionA to finish)
The solution is to install one solution, wait for it to complete, then install another. There's some samples of how to wait using the JobExists property on the solution here: Detecting Solution Deploying Status. It's not really any slower to do it this way (no more than your waiting interval), because behind the scenes SharePoint runs one job and then the other anyways when the locks are properly acquired.