You are correct, expect to have a database of a minimum of 500MB with 2.5M entries, but these tokens are shared, so with the same spam hitting the server, it doesn't grow that much.
SQlite could be a good solution as well, but it's not a big problem if MySQL is down for a few seconds during an...