Interesting. I agree with your statement regarding it being an NP-complete problem, as intuitively it seems that way, but do you have a reference by chance? Thanks!
Ok, so we can view register allocation as being a case of graph colouring; create a graph where the nodes are your 'virtual registers' and there's an edge between two nodes if those registers are both live at the same time. Then we can run on n registers iff we can colour the graph with n colours. This is one of the first identified NP-complete problems.
