A lock-free priority queue in C#
Generally, it's a bad idea to write this kind of code yourself.
However, if you really want to write this kind of code, I say take a page from Eric Lippert's book (or blog, as it were) (web archive link), where basically, you would implement the queue but instead of having all the functions that make modifications on the queue modify the instance you call the method on, the methods return completely new instances of the queue.
This is semantically similar to the pattern that System.String uses to maintain immutability; all operations return a new System.String, the original is not modified.
The result of this is that you are forced to reassign the reference returned on every call. Because the assignments of references are atomic operations, there is no concern about thread-safety; you are guaranteed that the reads/writes will be atomic.
However, this will result in a last-in-wins situation; it's possible that multiple modifications are being made to the queue, but only the last assignment will hold, losing the other insertions into the queue.
This might be acceptable; if not, you have to use synchronization around the assignment and reading of the reference. You will still have a lock-free-priority queue, but if you have concerns about thread-safety and maintaining the integrity of the operations, you have done nothing but move the concern about synchronization outside of the data structure (which is almost all cases, is a good thing, as it gives you fine-grained explicit control).