John,
Not to tell you how to configure your network (everybody has different ideas and experiences) but here is some food for thought:
If you have two ends of a connection that are both going to be the same no matter what, why leave it up to Auto-negotiation? What is the overall benefit to everything involved?
Certain operating systems and network gear, while claiming to be highly capable of auto-negotiation, seem to have issues successfully determining the appropriate mutual speed. While that may cause limited issues on the outer fringes of the network, it can wreak sheer havoc on the core and the issues can be a real monster to track down since the issues are usually seen on the outer rim and we always start looking where we see the errors, not at the core.
I don't know the scope of your network and I have NO idea how large of a task this would be, but it seems as if you have spent a great deal of time in the troubleshooting process already. Perhaps it would be more prudent to start hard-coding the ends of the network links that are known to most likely remain static as you are chasing down errors (is that the port with the problem? -- No? -- Static it now and move on...). I would even include servers in this if it were up to me since they are likely to be in place for a long time to come.
What you should ultimately end up with is nothing but fringe devices (PC's, laptops, etc) left on Auto-negotiate with a solid core that doesn't have to worry about it any longer.
Just a thought,
John