Попробуйте эту логику c:
SELECT *
FROM yourTable
ORDER BY
FIELD(Status, 'New', 'Updated', 'Deleted'),
CASE WHEN Status = 'New' THEN UNIX_TIMESTAMP(app_date) ELSE -1.0*UNIX_TIMESTAMP(app_date) END;
Первый уровень сортировки помещает новые записи перед обновленными записями и обновленные записи перед удаленными записями. Второй уровень сортирует по возрастанию по дате для новых записей и по убыванию для всех остальных.