Why are those estimates way off?
I believe this is due to all the ORs in your WHERE predicate on the Record.Tag field. It's causing a bad cardinality estimate. That is a rather long predicate and set of ORs, could you try breaking it into multiple smaller queries for different sets of Tags and the. UNION ALL the results of each query back together? It may help with the cardinality estimate.
You could also then change the ORs for a range when you break it up to make it less verbose at least, such as:
WHERE Record.Tag &gt;= 10400 AND &lt; 14006