in the game, he's really annoying. i had trouble beating him too. just like u said, by the time you get back to him he's already healed a pretty good portion of his health.
*in the anime, i think he's an alright character. although i'd like them to expand a bit more on his character.
If only he had the constant hp regain in vs mode then I'd be him all the time, but fighting him with it is a real pain in the butt. Dam you you coward Kabuto!