My understanding is similar to yours - SQL shouldn't let you run the same job twice at the exact same time. I have tried doing this and it gives me an error.
As a thought, do any of the jobs start each other? Or do you have a different server that is starting jobs on this server?
I am just wondering if maybe something else is starting the jobs, even windows task scheduler?
Not sure if you can do this, but is it possible to disable one of the schedules on a job that runs twice and see if it still starts without a schedule? Even just running it manually for a few days to see if it does start automatically on you.
When the jobs are running duplicate, it is 2 different SPIDs for them but the same login, correct? I am thinking here that it might be something weird with threading.
Also, do you notice a pattern by looking at a larger time frame for the duplicates? Like that job A runs twice on Monday or on the 13th or on the 2nd Friday of the month or anything like that? I am wondering if maybe it isn't random, just difficult to see a pattern.
Another thought - can you reproduce this on a test server? That is, can you build up a test server and reproduce the problem? If you can, that is a good starting point as you can schedule things and do a bunch of testing.
Last thought - are you patched to the latest CU? I am not aware of that being fixed in a CU, but it might be a bug that was fixed. Likely not or I'd expect more people to be responding with "I had this happen too", but could be something specific about your schedule setup.