Stats are always slightly out-of-date. If you gather stats on an empty table, then insert a row, optimizing as if the table was empty could lead to catastrophically wrong results!
The only way to know for sure what's in the table is to run the query - which in this case is a full table scan.
An index on
might help here (if the COTS provider allows you to create these). As the optimizer expects few rows, searching this index is a good strategy.