Автор, зря вы считаете что организация очереди отложенных задач с помощью крона и базы данных это не очень хорошая идея. Это хорошая идея. Данный подход прост, популярен, эффективен, используется довольно широко. А вот о подходе с динамической постановкой/удалением задачи в крон из пхп я слышу впервые и он попахивает костылями имхо.
Вас зря смущает, что "крон задача будет ничего не делать 99% времени". От того, что скрипт каждую минуту будет запускаться по крону, смотреть в бд есть ли для него работа и, если нет, завершаться - не будет никаких негативных эффектов, это практически не потребляет никаких ресурсов.