Kadokawa Pictures USA (division of the Japanese company) owns the rights to Lucky Star, Full Metal Panic, Haruhi Suzumiya, Shuffle! and a number of other shows. So while Bandai puts out Lucky Star and Haruhi and Funimation/ADV puts out FMP and Shuffle (all of these shows are referenced/parodied in Lucky Star, though some more than others), Kadokawa USA is still the rights-holder and can facilitate such parodies.

I didn't know about the US law regarding parodies, though. I suppose parody is a different beast than something like Super Robot Wars or Jump Superstars or Tatsunoko vs Capcom.

Sgt Frog is another anime that has some pretty heavy references to other stuff, though it was mostly related to Gundam. And that's supposedly coming soon.