I feed mine krill soaked in zoe, selcon, or garlic (alternated) and he loves it (it's a good thing he can't get out of the tank, because otherwise he'd follow me all over the house).
With regard to the cleaner wrasse's, from what I've read there's another issue aside from their propensity to die/starve in captivity. I've heard the harvesting of this species in any quantity has a significant, negative impact on the reef ecosystems from which they were taken.
I'm not an expert...but if you have a species that "usually" doesn't do well in captivity, and possibly hurts the delicate reef ecosystem if removed...why not just use a cleaner shrimp or goby instead???
Bluto