Most MMO's use a combination of server and client side testing. Where the client uses its collisions locally, but the server "double checks" the clients movement. If the client is allowing invalid movement then the server corrects this by adjusting the clients position within the world.

As far as how to do this the fastest way possible, an in memory table or list containing most of the possible collisions and using quick lookups is the fastest way to go about this. The basic idea is build a list of all "blocks" and collision vectors that affect them, then test the position against the known blocks. If no match is found then its likely that you don't have a collision. Now you can move to local collision by testing immediate neighbors, if none found then no collision has occurred.

Its also good to do predictive collision detection when you have processor time. Thus calculate any collisions along a given path in the time you have alloted. If you find one, then you store it some place (in your memory block if its static, or in your local chances if its with something like another player).

Remember, just because things move doesn't mean that they are not static when doing collision detection. A perfect example would be a gear in a grain mill. While the gear rotates (thus moving the teeth) the pattern is very fixed and can easily be stored. The collision vectors in your list need to be generic (if your within N of me then we are considered equal).

One other note, most MMO's push local collisions off to the client completely. The server doesn't really care if you "run over" another player, this isn't a game threat. If you run through a wall is another story.

Final note, 2D collision is faster then 3D. Using a 2D collision system that is double checked with by its 3D counterpart may be better then actually using a 3D all of the time.