They say they are multiplayer-compatible, but I don't see any online games listed when I try to play Internet Games. What's wrong?

To see a internet game with that mod there need to be one. If no one is hosting a game using the mod, there is nothing to see. What mod are we talking about here btw ?

All people in multi-player MUST be using the exact same version and mod of Civ4.

If you play any mod, you won't see people playing default Civ4... only the people using the exact same mod you are using.

The specific mods I've tried have been Varietas Deolectat, The Road to War, and Fall From Heaven II. I have a feeling enough people play those for there to be some games listed.

Sorry, but I'm bumping this. It's a problem several people are having, and needs answering.

Are you really certain that there was a open game at the time you searched (The only way to be sure would be if someone you know hosted that game...)

I had played games with Mods (Tho none of th emods you mentioned) online, so i know it does work at least sometimes. However there are usually not many (like in zero) open games with mods, unless a "event" is planed with a few people i know.

Not sure. However, to test that, I'd need to organize a game here with several other players, and see if that does show up. In fact, I think C&C should have a subforum for organizing games using mods.