Basically, as ripper said, Magic isn't a perfect information game. Each players knows things the other player doesn't (for example, the cards in his hand) and thus to prevent cheating you'll need a mediator with perfect information. This means that every action that involves luck or chance (drawing cards, flipping coins) has to go through the mediator. The process would then be something like this:

Player one says to mediator, "I draw a card". Mediator tells player one which card he drew and informs player two of the draw. Player one tells mediator "I play a Mountain". Mediator verifies that player one indeed has a mountain in their hand and acknowledges the request, announcing to both players of the new card on the board.

As you can see, this can get very tiresome with a human mediator. A computer mediator such as MTGO or even the one provided by MWS would do (note that the mediator doesn't have to understand the rules of the game, only keep track of which cards are in which zone).

As for priority passing, there are actually rules for that:

713.2. Taking a shortcut follows the following procedure.

713.2a At any point in the game, the player with priority may suggest a shortcut by describing a sequence of game choices, for all players, that may be legally taken based on the current game state and the predictable results of the sequence of choices. This sequence may be a non- repetitive series of choices, a loop that repeats a specified number of times, multiple loops, or nested loops, and may even cross multiple turns. It can’t include conditional actions, where the outcome of a game event determines the next action a player takes. The ending point of this sequence must be a place where a player has priority, though it need not be the player proposing the shortcut. Example: A player controls a creature enchanted by Presence of Gond, which grants the creature the ability “{T}: Put a 1/1 green Elf Warrior creature token onto the battlefield,” and another player controls Intruder Alarm, which reads, in part, “Whenever a creature enters the battlefield, untap all creatures.” When the player has priority, he may suggest “I’ll create a million tokens,” indicating the sequence of activating the creature’s ability, all players passing priority, letting the creature’s ability resolve and put a token onto the battlefield (which causes Intruder Alarm’s ability to trigger), Intruder Alarm’s controller putting that triggered ability on the stack, all players passing priority, Intruder Alarm’s triggered ability resolving, all players passing priority until the player proposing the shortcut has priority, and repeating that sequence 999,999 more times, ending just after the last token-creating ability resolves.

713.2b Each other player, in turn order starting after the player who suggested the shortcut, may either accept the proposed sequence, or shorten it by naming a place where he or she will make a game choice that’s different than what’s been proposed. (The player doesn’t need to specify at this time what the new choice will be.) This place becomes the new ending point of the proposed sequence. Example: The active player draws a card during her draw step, then says, “Go.” The nonactive player is holding Into the Fray (an instant that says “Target creature attacks this turn if able”) and says, “I’d like to cast a spell during your beginning of combat step.” The current proposed shortcut is that all players pass priority at all opportunities during the turn until the nonactive player has priority during the beginning of combat step.

713.2c Once the last player has either accepted or shortened the shortcut proposal, the shortcut is taken. The game advances to the last proposed ending point, with all game choices contained in the shortcut proposal having been taken. If the shortcut was shortened from the original proposal, the player who now has priority must make a different game choice than what was originally proposed for that player.

These happen implicitly all the time in face-to-face games, but will need to be formalized in games played over distance. Again, player one might say "I propose to move to the beginning of the next turn" to which player two might respond with either "I accept the shortcut; I untap my permanents and draw a card" or "I shorten the shortcut to the beginning of your end step; then I play X". Basically, any message exchanged in the protocol acknowledges the previous shortcut and proposes a new one; any subsequent action by the other player assumes the shortcut has been approved, unless explicitly stated otherwise.

This allows two players to conduct a game almost as if they were face to face in the sense that it conserves messages for uninteresting events ("I pass priority" - "I pass as well"). Players would have to be careful so as not to divulge any information in their shortcuts: for example, if a player says "I attack with creatures A and B" and the other player responds with "I shorten the shortcut to the declare combat phase and play X on B, preventing it from attacking" then some player one "gave away" some information he didn't have to (maybe player two wouldn't have played X if he didn't know B was going to be declared attacker).

Note however that this kind of information leak happens all the time in face-to-face games as well (when was the last time you heard someone say "I declare combat and pass priority, do you want to do anything?"), and players just have to choose their own path between letting the game flow or being as secretive as they can. The problem is increasingly apparent in online MWS games where players usually skip phases all the time (with the notable exception of the "end my turn" convention, allowing players to play end-of-turn moves).

So basically, yeah, you can play Magic over a distance, given an unbiased, fast mediator, a quick way of exchanging information and/or keeping reference (most probably internet-based). You basically just need something like MWS, only with players being able to keep a connect, make a move, then disconnect whenever they please (where the game state would persist over time on some server until explicitly shut down).