Some weird pairings I have seen:

Pearl Jam w/ Cheap Trick opening
Rush w/ Candlebox opening
Pearl Jam w/ Steve Earl opening (man did he suck)

Last year The Mars Volta and System of a Down did a small tour together.