In the general case you're right, it's equivalent to the halting problem. The outline of the proof by reduction: set up two communicating processes in a way that will deadlock iff a particular loop in one process fails to terminate. So if you had a deadlock detector for arbitrary communicating processes, you could use turn it into a termination detector for arbitrary loops.

Yes, deadlock-free lock systems are an ordinary part of OLTP database engines. They don't prevent deadlocks per se so much as detect them and dynamically resolve them.

The mechanism is costly but elegant. If a lock you are trying to acquire is owned by another thread, you inspect the locks you own to determine if that thread is waiting on one of your locks. When a deadlock is detected, there are several strategies to automatically resolve it e.g. rolling back one of the threads to a point where forward progress can be safely serialized.

No one wants to use these mechanics for ordinary code, due to their cost. For the fashionable thread-per-core software architectures, deadlocks aren't something you commonly have to worry about.

Only if the priority is flat and not some sort of graph, is my guess.