Interestingly, the server thing isn't much of a barrier. You can add someone as a friend/contact regardless of which server he's on, and also invite him to your party. Guilds are cross-server as well. Given how likely you are to be placed in an "overflow" server anyways, you aren't always in the same..."phase" (for lack of a better word) with other people from your server either.
If you're in a party with someone on a different server or overflow, you can go to the same area he is, right-click his name, and select "Join In" to be in the same phase alongside him. I've joined in an instanced Personal Story mission thing with a friend from a completely different race and server, and did normal exploring and leveling with him after that.