It seems that no matter what I do when playing allied maps the alliances simply don't work, I remember playing in the past (although it was the windows 95 version) and alliances did work. Anyone have any idea what's up with that?

They're bugged anyway, allied AIs will keep stealing your mines.

I have windows version as well, but the alliances didn't work there either.

Or you could try fheroes2, the HOMM2 open source mod project, which includes, sharing maps between allies, being able to visit allied towns and mage guilds, and trade troops with allied castles and heroes (actually you are allowed to take troops for the moment =). Also, code is in there to prevent allied heroes stealing allied mines. Currently there are no campaign facilities or internet multiplayer (just hotseat and single player), but they are are on the list and will definitely come. A feature that is likely to come relatively soon is "Battle Only", which I think is a preset battle that you play out, rather than a whole map. A new fheroes2 Editor is going to be made too, with maps with more squares than the biggest two-layer H3 map possible. The game is getting better all the time! For more information, see here.

Have fun! =)

Best regards,
Steven.