If you award xp for the PCs defeating foes (not necessarily killing them), then they should get XP twice. He knows what to expect, and he will probably have a slight upper hand the next time around...ie he knows to send his minions after the mage, or to ignore the guy who took too many multi-class levels and can't hit the broad side of the barn, or to send the 4-legged animal companions after the monk who likes triping people etc...
You're perfectly able as the DM to use fiat to enable him to find some more minions or better replacement gear, and you're encouraged to do so. The players have no way of knowing you manually adjusted his stats a bit, or that he wasn't actually a friend of evil wizard Bob before you decided he was. Even if it is as simple as him borrowing a potion or 2 from 'someplace else in the dungeon'. Suddenly the bad guy with 4 more pts of AC, or who hits for 2 more pts of damage can pose much more of a challenge to the PCs. And they won't feel like they killed a clone of the last chump they beat down.
Incidently....how did he get away the first time? Did he regenerate or something and the PCs didnt notice?
I always play dumb as a PC and pretend like nothing regenerates....until the first time it happens in game. Then we all pretty much assume that everything regenerates and they get CDGd or heads chopped off etc...well at least for the exotic monsters. They usually make nice boots anyways

I'm a big fan of adorning my characters with critter-parts, lol.