Т.к. база и файлы, как правило, лежат на разных серверах, идеального решения нет.
Всегда возможен технический сбой на любом из этапов.
По-хорошему, решается cleanup-скриптом, который раз в неделю пробегал бы по всем файлам и удалял те, которых нет в базе.
И согласен с тем, что следует сначала удалять из базы.