Вопрос: Как сделать правильную организацию «напоминаний» на уровне БД?

Лучший ответ: Как бы я это реализовал:
В произвольном, удобном для Вас виде храним периодичность (можно как Вы написали в первом варианте, в формате крона). Дополнительно, отдельным полем храним дату следующего наступления события. Соответственно все выборки ведем просто по дате.
Это для случая если у задачи нет cтатуса выполнения, не нужно смотреть на прошлые/будущие задачи, итд.
Если хочется сделать как в google calendar / icloud - где каждый экземпляр этой повторяющейся задачи по сути достаточно независим - становится чуть сложнее.
Получается 2 таблицы: задача-прототип где хранится периодичность, дата первого запуска и опционально дата последнего, - и задача-экземпляр где хранится конкретная дата и ссылка на прототип.
Сумбурно получилось, не проснулся еще :)
Если что - давайте обсудим :)

Худший ответ: У меня это так реализовано. Все даты храним в формате таймстампа, это проще для хранения и вычислений. Исключения храним в произвольной форме ключ/значение, у меня реализованы только часы ключами from to. Задания бывают в нескольких состояниях: активная, неактивная, просроченная, будущая, бесконечная.
Само задание выглядит примерно так (это как раз и есть запись в таблице):
 - старт - дата старта (таймстамп)
 - дельта - смещение реального старта от начала старта (это особенность моего приложения, нафиг не нужна, просто чтобы код не портить)
 - период - период повторения (таймстамп в виде timedelta)
 - продолжительность (должна быть меньше или равна периодутаймстамп в виде timedelta)
 - стоп - дата окончания (может отсутствовать, таймстамп в виде timedelta)
 - count - число повторений от даты старта (если есть, то обязана ставиться дата окончания, int )
 - исключения (например без понедельников или только чётные часы, или время с 10 до 19)
 - активна (да/нет)
Работает так.
- Выбираем все активные задачи, где старт меньше нужной даты и стоп равен нулю или больше нужной даты.
- Пробегаемся по всем заданиям и для каждого рассчитываем попадание в нашу дату.
- Если есть исключения, смотрим, не попадаем ли в них.
- Если есть count, рассчитываем его
- Если вместе с count стоят исключения, то пересчитываем count для каждого периода - самый ресурсоёмкий процесс, приходится пробегать по всем интервалам с начала старта.
Базовый класс (на питоне):# функция преобразования питоновского класса datetime в timestamp
# возвращает timestamp (int)
def total_seconds(td):
    seconds = (td.microseconds + (td.seconds + td.days * 24 * 3600) * 10**6) / 10.**6
    ret = 0 if seconds < 0 else seconds
    return ret

class interval(object):
# здесь должно быть все понятно
# self  - указатель на сам класс, особенность питона, на другом языке этот параметр опускаем
# вместо self на других языках используем this или аналог
    def __init__(self, start, delta, duration, period):
        self.start = start
        self.delta = delta
        self.duration = duration
        self.period = period

# вычисление последнего интервала от нужной даты
# возвращает две даты от и до
    def last(self, date):
        _start = self.start+self.delta 
        mul = int(total_seconds(date - _start)/total_seconds(self.period))
        at = _start+(self.period*mul)
        to = at+self.duration
        return (at,to)

# является ли интервал активный на нужную дату
# возвращает true/false
    def isLive(self, date):
        at, to = self.last(date)
        f1 = date >= at
        f2 = date < to
        return f1 and f2

# вычисление следующего интервала от нужной даты
# возвращает две даты от и до
    def next(self, date):
        at, to = self.last(date)
        return (at + self.period, to + self.period)
Остальное, не привожу, так как много и надеюсь, допишите сами.