To me, whether it's NP-complete is of little concern, since humans have been allocating registers (and beating compilers) with little difficulty. On the contrary, I feel that being labeled as NP-complete has somehow slowed the development of better RA algorithms, on the basis that it's "too hard". There's a saying "one of the first steps to accomplishing something is to believe that it's possible", and if people believe that RA is a more difficult problem than it really is, then that has a discouraging effect. NP-completeness is only related to the complexity as the problem size increases, but in practice the problem sizes aren't that big --- e.g. within a function, having several dozen live variables at a time is probably extremely uncommon, and machines don't have that many registers - a few dozen at most.

I think the human brain is probably Turing-equivalent, but it also likely doesn't matter -- if I can describe the algorithm that I, as a human, take to perform compiler-beating register allocation and instruction selection, then a machine can probably do it just as well if not faster than me since it can consider many more alternatives and at a much faster rate.

I agree that heuristic approaches are the way to go, but in a "too far abstracted" model like graph colouring, some heuristics just can't be easily used; e.g. the technique of "clearing the table" --- setting up all the registers prior to a tight loop, so that the instructions within do not have to access memory at all. Using push/pop (x86) for "very ephemerally-spilled" values is another one.