I was consistently receiving MySQL "Packets out of order" error messages when attempting to connect to MySQL, mostly on my AJAX pages, but I couldn't attribute it to anything or reproduce it in any way. I did notice, however, that when switching MySQL persistent connections from on to off, the problem went away.
Lots of Google searches later, I found lots of articles and forum posts saying that it was an issue with the my.cnf configuration setting, and to tweak max_connections, etc. Then our sysadmin found an article saying it was an issue with the version of MySQL + PHP we were using together. There apparently are lots of causes for this, and the fact that it wasn't reproducible made it all the more difficult to debug.
Well, I finally figured out what the cause was, and so I'd like to share it with you, at least in our case.
On Persistent Database Connections in the PHP manual there is a warning blurb with a red background that says that you should never use persistent connections if your script uses transactions.
Well, that was it! We do, indeed, use transactions. I've made an adjustment to no longer use persistent connections when using transactions, and the problem miraculously solved itself!