A regular process (probably triggered by cron) would then delete old entries from the database.

You can avoid this by calling the purging mechanism each time you generate or go looking for a link. Moreover, I'd put this purging call before the actual search for the required item, so that you can get rid of the WHERE clause.

   $dbh->do('DELETE FROM tmp_downloads WHERE expiration < NOW()');
   $dbh->prepare('SELECT * FROM tmp_downloads WHERE token = ?', undef,
+ $token);
   # ... and so on...
[download]

I think you're willing to accept the slight race between the DELETE and the SELECT - it would mean that a particularly lucky guy could download stuff in the very few instants between the two queries if the expiration happens right in the middle :)