I didn't truly know and I didn't want to just throw out a guess so I just asked. They mentioned they have a basic hand rolled system for their physics. So not using unity physics.
I guess making the claim that is was more complicated might have not been right for me to do, but it would be hard to believe that they did the degenerate case of O(n^2).
Speculation: I have only written a physics engine once during college (so please excuse my ignorance), but I think for a basic mmo a simple chunk and AABB approach would work. It would be easy to query for the surrounding chunks and just run the collision on that subset. I know one of the team members was working on porting a minecraft 1.7.3 server at one point, but I don't know if they got up to the point of moving collision off of the server and into the database.