Making him "that" powerful might be a little too much.
I'd suggest a Elite Controller/leader, using a power similar to the pit-fiend's minion bomb. I mean, when a guy can just tell one of his men to blow himself up, it's a sign of power. I'd say make it 3d10+6, burst 1 around the minion, target being an ally within burst 5-10
Have him constantly surrounded with minions, of course.
Also have a power similar to the Mind flayer's "thrall imposition"-thing, making him very tough to kill as long as he has flunkies.
He's a pirate, give him a recharge

magical portable cannon that shoots lasers, or something. Range 10, 4d8+6. and for added fun, push 3
Also, he has a fancy flintlock pistol that deals 2d8+6 at range 10.
Finally, he'd have a necrotic cutlass, dripping with shadowstuff, deals 1d10+6 and eats a healing surge from the target.
I have to say I like Cadfan's doppleganger idea. Although I've seen it done so many times before.
I say RP-wise, always have an escape plan, always be perfectly in control, and set traps all over the place.
The players enters the room, it's made out of stone, but the stone on the ground are cracked, old and shaky. They floor won't collapse under the players weight, but if anyone attacks the floor, it makes the player fall for X feet (save cancels fall but makes prone). Of course, area attacks (such as suicidal minions) punch huge holes in the ground.
He'd be raining down death on the players from a hard to reach ledge, higher up (medium athletic DC, 10 feet up). Anyone who tries to get on top gets blasted with a cannon shot to the chest (thus fall down, most likely punching a hole in the floor, good times)
Plus, constantly send hitmen and mercenaries on the players the second he starts considering them a threat (probably not before they've seen him in person, if they don't, they're just nuisance). And have them live just long enough for them to reveal who sent them. The players will positively go on a revenge quest soon enough.
Plus, you'll be able to send them anywhere you want just by going : Oh, he went that way!
Last, but not least, if you ever player Ninja Gaiden 2, when you cut off an evil ninja's leg, he tries to stab you with an explosive shuriken and go all murder suicide. Add a warcry for "organization's name" before, and you have a bunch of very fightning little guys.
Little things scare more then fanatism, simply because nobody is truely prepared for it.