What if it were not a tile-based game?
Whether the game is tile based or not, you would be sorting the mobile game objects into a grid or something similar, to optimize object interactions.
---
Regarding discussions about how many concurrent players a single conventional server can handle, I recommend reading this blog http://eternal-lands.blogspot.com/ by Radu Privantu, the guy who runs the Eternal Lands mmo. Theory and discussion are all well and good, but hearing about the experiences of someone who has had a working game running 'in the wild' for several years is more useful.