Gyarados and Jirachi cover each other real well. Salamence and Magnezone cover each other just as well. Heatran and Celebi cover each other perfectly.
I'll edit if I can remember any others.
Edit: I can't believe this one slipped my mind, especially since I actually use these two: Salamence and Heatran. Salamence and Scizor work alright. Heatran and Gengar work well, since Gengar is immune to ground and fighting attacks, while it can also take most water hits from bulky waters (surprisingly). Most of these combinations are pulled from my team.
There are some combinations that aren't quite as awesome as some of the above, but they're fairly effective:
Gengar and Scizor can potentially work. It depends on how you look at it; from a purely typing-effective it's a one-way deal, since Scizor can take Gengar's weaknesses, but it doesn't work so well the other way around. If you look at it from a metagame standpoint, people generally attack Scizor using ground, fighting, or fire attacks, even though he's not weak to 2 of the 3. Gengar can come in on the first two attacks, if you know that they're going to use it.
Heatran and Vaporeon work fairly well. Jirachi and Vaporeon work...to an extent.
Note on Scizor and Heatran: When using Scizor, Heatran isn't always the best answer to turn to, because as stated earlier, most people try to hit Scizor with fighting, ground, or fire attacks, two of which Heatran is weak to.
If any others come to mind, I'll make another edit.