Strange we'd never discovered this before, but as it turns out, all OpenMRS objects aren't getting properly serialized when using standard Java serialization.
If you specify that a superclass implements Serializable, then all subclasses will also be serializable and adding "implements Serializable" to the subclasses is redundant.
However, if you mark a subclass as Serializable, it turns out that any properties of superclasses aren't serialized. In OpenMRS we mark the subclasses like Person, etc, as Serializable, but BaseOpenmrsData, BaseOpenmrsMetadata and BaseOpenMRSObject are NOT marked as serializable, so therefore when serializing an object the uuid and associated auditable information are lost. Simply adding "serializable" to BaseOpenObject corrects this problem.
Note that this does not affect serialization via XStream, probably why we haven't noticed it before.
For those that are curious, this issue does manifest itself whem tomcat serializes sessions during a server restart. We discovered if a user is logged in and a server restart occurs, then after restart Context.getAuthenticatedUser.getUuid() returns an incorrect, random uuid. (Which was screwing up the synchronization via the sync module, for what it's worth)