A single RewriteRule can rewrite all requests with a "_ " in to a special PHP script that runs only for those requests.
RewriteRule _ /special.php [L]
This new PHP script then serves the required 404, 410, or 301 HTTP response code based on rules you program into that single PHP script.
It can get its data to do that either from an array you create, or from the database that runs the site.
This method slows the server down almost nothing. Only one extra rule is parsed per HTTP request.
Adding thousands of individual rules, one for each of your errant URLs, would slow the server down considerably. Additionally, this method will be almost impossible to maintain if there's more than a couple of hundred URLs involved.