Jeg tror ikke, det kan blive renere end dette:
ORDER BY priority=0, priority
SQLFiddle Demo
Bemærk, at i modsætning til alle andre løsninger, vil denne drage fordel af indeks på priority
og vil være hurtig, hvis antallet af poster er stort.