@Al, if I understand what you are describing correctly, it is not metagaming, at least not the inappropriate type. Using a relationship from a previous game isn't fair because you have that relationship with another player while the other participants in the game don't have that. The difference with the information available in a regular non-anon game is that everyone has access to the same information. New players can look at your record, realize you aren't going to honor an alliance with them and use that against you if they want. You can look at their record and do the same type of analysis. It's metagaming, but it's allowed since the information is available to everyone and there are no guaranteed alliances from it. Like you said, if you play with a good new player you'll consider allying with them. Now deciding you will always ally with someone isn't allowed, since going into the game everyone doesn't have a chance to gain an alliance with you. Does that help?
@Krellin, YJ, and Draug, making that kind of offer is metagaming whether or not you're lying because regardless of your intent, the person who you made it too is now basing their decision on factors outside of the game. This type of metagaming is allowable in some tournaments on this site, but other then that it's unfair to the other players in the game. The big problem with this is that it typically starts out as "hey I'll help you out in this game if you help me here" and then turns into "well we owned in those two games so lets start this game and wipe the floor with everyone else". Obviously everything is on a case by case basis, and we aren't going to judge the first type with much more then a warning unless the player clearly knows better or has been warned about site rules before. The second type, joining games with preconceived alliances though is more severe, and the more games it's done in the more severe the punishment.
@dD_ShockTrooper, only admins can check private messages, and it's almost never needed. The other assortment of mod tools make discerning innocent ignorance of metagaming, and outright cheating pretty easy. Like 2ndWhiteLine mentioned, most of the time the other players in the game are pretty quick to realize when something is wrong. Metagaming cases are usually as simple as getting an email like this "Turkey told me he won't ally with me because Russia is his halo partner", etc.
What's interesting is that the metagaming between two players who meet online like everyone is describing is rare because the random country positioning often makes alliances impossible, and people quickly realize it's in their best interests not to force an unusual alliance.
The final point being, we have a lot of tools and experience figuring out people's intentions. There's no harm at all in reporting a game that looks suspicious. The worst that will happen is the mods spend some extra time looking into something, and we all know most members don't mind wasting mods time ;). Best case is that you save a lot of other games, including yours, from being wrecked by unfair play.