Thanks to a suggestion from Mohammad Lahlouh, all deleted comments are restored. Thanks!
I was able to do this with the mysql binlog, which is a binary log containing all statements executed on the server. If you face a similar problem, here are the steps to restore the DB:
See if you're actually storing binlogs. For me this happened to be the case, although I never actually payed attention (My friend Jens Meijer is so kind to provide hosting for me). In my case they were stored in /var/log/mysql.
Grab your latest backup. In my case it was from October 2008.
Make sure you also create a new backup, just in case this process goes wrong.
Restore your old back.
Find the binlog that corresponds to the date of your backup. I did a simple copy of the ~300 binlogs to a different directory.
Run the binlog through 'mysqlbinlog' and pipe into a new file. I had to append the --database argument, because I wasn't interested in all the other databases. The full command for me was mysqlbinlog mysql-bin.* --database evert2 > commentsbinlog.sql