Не мисля, че може да стане по-чисто от това:
ORDER BY priority=0, priority
Демонстрация на SQLFiddle
Имайте предвид, че за разлика от всички други решения, това ще се възползва от индекса с priority
и ще бъде бърз, ако броят на записите е голям.