You're close to right. There's been a lot of work on completely non-spatial distributed server architectures (mostly using distributed hash tables and occasionally multicast between servers) but they don't scale as well as expected. There's a reason for spatial partitioning - things close to each other tend to interact more.
Fixed partitioning is the easy way to do spatial partioning - you drop boundaries and migrate objects that cross them. Often you use design to allow interaction between partitions to be ignored, so you don't need any communication between servers besides migration. Dynamic partitioning would largely solve this problem (as, generally, you're never actually in a region where you can interact with more than a several dozen other players) but is HARD if you want consistency.
Guaranteeing instantaneous consistency is impossible - you've got hundreds to thousands of servers and keeping them all in lockstep at 30Hz with a potential for same-frame interaction between objects just isn't going to happen. Instead, what if you thought of the game as a simulation of abstract moore machines. Every frame each object looks at the state of of the wold and then sets it's state for the next frame and maybe creates other objects. Inter-object events can be modeled as objects that exist for a single frame and the receiver looks for. This means no instantaneous inter-object communication, but that's generally acceptable and likely unavoidable.
Now, network latency between servers could still be a problem: as the system grows it's impossible to keep it in lock-step even with the slightly relaxed communication requirements. This can be solved by employing a technique used in distributed databases: eventual consistency. Lets explicitly allow inconsistent state to exist between servers instantaneously, but guaranty that it will be eventually be resolved. Lets have objects use a subscription model for their observations and send those subscriptions to all servers that might contain matching objects. When a server sees an object matching a remote subscription it sends over the object with enough state to run a dumb predictor (that can't look at the dynamic state of any other objects). The server with the subscribing object can then use that state and predictor to keep the object in sync and then service the actual subscription. Back on the server with the object that mached the subscription, it makes a local copy of the proxy it sent. It updates the copy along the the rest of the work, and compares it with the real object to detect when the remote server made an incorrect prediction. In this event, it sends an update to the subscribing server with the new state.
Now you should say, "Wait! That update won't arrive until the server had already run the simulation for that frame!". Yep, you're probably right. However, because there's this subscription data available, the server can very efficiently re-run the simulation, touching only objects that might have detected the change (and any consequential changes). This might cause further updates to other servers, but because of generally sparse nature of interactions in games, the state on all servers for a given frame will quickly be consistent.
This was almost my thesis before I got pulled into graphics and wii remotes. If this interests you and you'd like to see an early paper about it, drop me a line: [my_username]@[my_username].org.
