Maybe it was not so smart to do after all to remove all files in the QMail queue while QMail was running.

The following solution did work for me, but is often a no-go since I just remove the queue and recreate it with the queue-repair script (to be found in the mail/queue-repair in the FreeBSD ports).

1. Stop QMail:
   
   # /usr/local/etc/rc.d/svscan.sh stop
2. Move the queue away:
   
   # mv /var/qmail/queue /var/qmail/queue.old
3. Run queue-repair:
   
   # queue-repair -n -c -s 23

   The -n stands for not using the Big Todo Patch in QMail. Use -b if you do use this patch.
   The -c stands for recreating the database.
   The -s stands for the amount of subdirectories in the queue. Qmail's default is 23. If you want another number for whatever reason (performance), make sure it is a prime number.

4. And start QMail again:
   
   # /usr/local/etc/rc.d/svscan.sh start

Update 14 September 2007:

This is the proper way of clearing a QMail queue:

1. Stop qmail.
2. for i in bounce info intd local mess remote todo; do
   find /var/qmail/queue/$i -type f -exec rm -f {} \;
   done
3. Restart qmail.