To answer this, we'd need a couple of experiments:
- Cut him in half and see which half regenerates
- Cut him into more than two pieces of the same size/weight and see which regenerates
- Burn him until he stops regenerating
In one comic, he was burned to ashes using Napalm, so even living tissue in pockets in the andamantium would have been cooked, so the last one has been answered. I haven't seen him being cut enough because of his skeleton, though. Shooting his head doesn't kill him, either.
My current stance is that is ability isn't in fact linked to his body - if there is a body left, it will use it as a starting point but he would regenerate from thin air even with the whole body completely destroyed.
But to answer this, we'd need to know whether the authors at Marvel have an idea how Wolverine really works. Maybe they just make things up as the stories unfold and don't bother too much about continuity.
[EDIT] Just found this on YouTube: Wolverine: Five Facts You Didn't Know
Wolverine's healing powers evolved over time. At first, he could just heal simple wounds faster than average. At 1:50, he says: "After being caught in an atomic explosion, Wolverine was capable of regenerating all his tissue and muscle within minutes."
The important part starts around 2:00: "According to the Xavier Protocols, created by Professor X, the only way to truly kill Wolverine is to decapitate him and to keep his head far from his body."
From the Xavier Protocol:
Long range attack, sever the head, and place the head and body far apart.
Note: This assumes Wolverine is without his adamantium skeleton.
I'm not sure why the adamantium plays a role here. If the adamantium was just a coating or replacement of the bone structure, you can easily pull the neck bones apart after removing the tissue: They don't interlock in any way.
But if that was his weak spot, I'd design his backbone to prevent separation.