Moreover, as I mentioned in my OP, the fighter and paladin are easy to end run around once they get locked down by the creature(s) they engaged. Other enemies can maneuver around or just sit back and shoot past them.
I have not seen this at all. I played with a super effective fighter in my first long term 4e campaign. He was an Elven Fighter who specialised in spear and shield. This was before there was a ton of feat support for that, but he, through good power choice and tactical maneuvering, was an almost unstoppable wall. I know this because I was a Str Paladin, and I almost never ended up marking things because his mark was 10x better. I was a Defender in the "Scare them so bad that they need to kill you to sleep at night" type, not the good kind.
In a different campaign I switched roles. I played a fighter who used as many multiattack powers as I could to keep things marked and locked down. A post-DP charisma Paladin in that party was the off-tank, and his mark was very tough to ignore. Again, smart power and feat choice meant that even though I was the flashier tank, his mark was the deadlier and more important, and often his overwrote mine on the deadliest target.
My current campaign has a Swordmage. As far as traditional defending goes, they are kind of out there. Teleportation powers and multiattacks (where each attack does not mark) don't fit the mold of the staid defender, but because we have a mostly ranged and pretty mobile party, he is almost always the ready target, and when he isn't he pops next to the offender and whacks them one.
My experience has shown that good feat and power choice can turn you from an off-striker bag of HP's into a truly difficult challenge for any DM, and that is possible with a wide array of classes. Fighters do this naturally, almost without effort, but a well played Defender is not easily ignored. In your DM's case, I'd advise the defenders to boost the punishment phase of their defendery schtick. Better OA's for the fighter, with riders or extra effects. For the Paladin, powers that Sanction and debuff, as well as taking the necessary feats to keep his radiant retribution relevant.
If the DM continues to ignore the Defenders even after they have done this, all he is doing is killing his creeps faster. A fighter that is allowed to constantly make OA's and other extra attacks can approach striker level damage.
I had not considered this a problem, really. . .
Jay