Flygluffet: Yupp and tried it. We even tried gameranger but couldn't get it to work. We could host a lobby and start so that HoMM 3 starts but the other person never got into the lobby. Thank for trying. If I ever find and answer I'll make sure to post it.
I have one suggestion you could try. I've played via email, in an ad-hoc sort of way. We created the game via multiplayer, then each player saves at the end of his turn and emails the save to the next player. The honor system is involved; don't reload if you screw up (unless you have permission, of course), and don't scout the other player's stuff.
We use some remote connection software (I don't recall the name, off-hand) when we actually have a player-vs-player battle.
Just make sure each player loads the game as a multiplayer game, or the computer will take turns for the other people.