As for arcane characters, I agree having to take a feat isn't such a big deal.
But the Star of Corellon strikes me as representing a rather high cost - not only in the effectiveness department, but especially in the fun department.
(Having to give up the idea of making your main attack tool yield powers and properties just to make it work with your arcane bonus powers seems neither optimal nor fun)
Well, WRT to the Paladin/Warlock there are a number of choices the character can make in terms of implement use.
They could wield one of the divine weaplements (holy avenger or there are several others now as well). This allows avoiding needing a weapon and TWO implements. This would probably be suboptimal in that most Paladin/Warlock PCs will be CHA paladins and not really all that concerned with weapons. OTOH a character with a holy avenger COULD wield it in all three ways by taking AIP (heavy blade). This might be an option at high epic tier.
They could wield a weaplement sword by simply taking AIP (heavy blade) and using any type of magic sword, or by wielding a Pact Blade (sword). They would still need a holy symbol, but this is no different from the situation of most paladins and clerics anyway.
They could wield a Star of Corellon as their dual-purpose implement. This could even be combined with the above option and Dual Implement Spellcaster if one desired to do so.
In any case realistic Paladin/Warlock characters probably don't care about weapons anyway since they will have no big use for strength. In that case just wield one of each type of implement or again wield a Star of Corellon. Any character going seriously into warlock is going to want a rod anyhow though as a second implement, so what's the big deal?
Honestly, the supposed horrible nerfing people seem to believe they're getting at the hands of the implement rules really aren't all that big a deal. The vast majority of characters that are competent casters will be utilizing more than one implement anyway before long and there are various ways to combine these things. It isn't even much of an issue with a lot of combinations. Sorcerers dagger implement is a pretty decent weapon already for instance (and really, why MC Sorcerer if you aren't going to utilize daggers to a significant degree). Similar considerations exist with sword mages.
As pointed out by another poster above there is NO issue with PP powers, they will work with any implement.
There are a whole variety of weaplements too. Yes, they are mostly specific magic items, which means you sadly have to avoid the (now largely nerfed) bloodclaw cheese, but hey I'm shedding a bitter tear on that one.
As for the comparison with martial classes and using weapons with various class powers. It is a BIT more flexible but don't overstate things. Rogue powers work only with rogue weapons and likewise rogue class features. Sure you can be a Fighter/Rogue, and you'll still be using rogue weapons and still can't mix that with heavier weapons which would work better with most fighter powers. Just like implement users you can mix things around and dual wield, etc, but it has costs. The same is true with mixing in ranger powers, if you want to use them with ranged weapons, you WILL need a good primary dex and that's going to require some trade offs. Even Ranger/Rogue is making these trade offs by needing to use light weapons. A few nice possibilities exist like a TBF ranger MC rogue and wielding a rapier in each hand, but its still not having your cake and eating it too.