I have little experience in Paragon, but the DM throwing some curveballs at you could make things tougher. How are you all at Skill Challenges? Incorporated into Combat challenges? Split the party. Sure, you have 2 leaders and 2 defenders, but that means you can't focus fire as well and monsters have more rounds to wear you down. Instead of concentrating on more monsters that do more damage, the DM can try underhanded tactics. One of my favorites was a oneshot where I created an entounter where all the creeps had darkvision and a couple of them had the ability to create zones of magical darkness. Introduce difficult terrain features or situations that force the party to use less efficient tactics (like hostages or running battles).
In short, your party seems to have done a good job building PC's, now your DMs need to match you with encounter building. Ho hum plane jane encounters will be nothing to you guys, becuase you seem to not be plane jane yourself. Houseruling is a bandaid that treats the symptom, not the problem.
Jay