No creo que pueda ser más limpio que esto:
ORDER BY priority=0, priority
Demostración de SQLFiddle
Tenga en cuenta que, a diferencia de cualquier otra solución, esta aprovechará el índice en priority y será rápido si el número de registros es grande.
