When you aggro him two stealthed elites come out to attack the party as well. Make sure to take out these first because he summons more of them. Have an off-tank (paladin, shaman, druid, or extra warrior) ready to pick up the ones he summons so they don't destroy your healer.

Horde can do Deadmines too... Shamans are possible

Vancleef isn't too hard if done well. You'll have encountered harder bosses and areas in the instance, such as the large tauren captain who stuns, and the upper deck with Cookie and his friends. Apart from the rogues, he isn't too hard to kill. Just be prepared.
A mage can polymorph one, a rogue can sap one. Make sure your party is on the deck, as standing below can mean you can't cast as your target is not in view. The tank should attack Vancleef, with DPS backup. Perhaps get one party member to run around, with the 2 bodyguards following, while the other 4 bring down the boss. When VC is dead, it is easy to mop up the others.
A party of about level 20+ should not find killing this too difficult, provided your party is well-balanced (tank, healer, DPS) and can co-operate well.

Vancleef drops some really good loot, such as the famed Cruel Barb, a green polearm, and other good loot. He also drops a letter, starting a very large quest series which leads onto a reward - The Seal of Wrynn, a ring which will last you until about level 50!

Be sure to do this quest, whatever race you are. These items will last you for many levels. Even if you're horde, don't be put off, you can still get to DM if you're careful. Sadly, you can't do the quest.

If you get in too deep when you're fighting VanCleef, or just on the ship in general, there is a sanctuary that you can get to and wait for everything to retreat so you can regroup. There is a large wheel-like thing on the side of the ship about half-way up (you can't miss it). Jump in top of it, and nothing in this area can get to you; even the caster-pirates will run back and forth, and eventually give up.

Gryan Stoutmantle reminisces about this quest in Grizzly Hills.

<name>! I hardly recognized you in your new outfit. Still have that tunic... or did you take the chausses... or was it the staff? I can't recall, it was so long ago...