Regeneration isn't really complicated, we just need to separate it into parts.
First it turns all hitpoint except for certain types (in this case fire and acid) into non-lethal damage.
Second, it heals non-lethal damage at a set rate (in this case 5/round), except if this damage can only be healed by specific circumstances (damage caused by starvation, thirst, etc.)
Third, it allows re-attaching of removed body parts.
Fourth, it causes removed body parts that are not re-attached to regrow after a certain time (in this case 3d6 minutes).
Only the largest part of the body benefits from regeneration effects, so you don't get two creatures by severing body parts (this is the case with some oozes as a special ability though).
Although the rules do not state decapitation does not result in death, it is commonly accepted that it doesn't. I'd think that without it's brain the body would act rather stupid though.
Common sense dictates that you need to deal lethal damage to severe a body part anyway, so you'd need a flaming vorpal blade or something, and even then it can be argued that the vorpal effect does not deal flaming damage.
As normal a coup de grace can only be performed with a weapon dealing lethal damage.
Nothing prevents a creature with regeneration to heal normally. A cure spell will heal it's full normal amount of lethal as well as an equal amount of non-lethal damage. Natural healing will heal 1 hit point per HD per hour (6/hour for a normal troll), as well as 1 hitpoint per HD per full night's rest (6/night for a normal troll).
Regeneration does not affect any effect that is not hitpoint damage.
Sorry if any of this was already answered, but thought I'd provide it altogether in a single post.
