Understanding performance of highly unique WHERE clauses
What's probably going on here is that at some point, you ran that first query with a value that had a lot more than 500 rows - so many that it figured it was better to scan 10M rows than do hundreds of thousands of lookups to get the Name and INT109 columns. And then that plan got cached, and reused when you provided a different value which would've benefited from a different plan. SQL made an assumption that it would be better to avoid recompiling than to evaluate each different value you could provide.

When you wrote a different query, it evaluated it fresh, and gave the best plan, although that might not be ideal for a different value. 

The best way to fix this is to have an index on (TYPEID, INT109) INCLUDE (ID, Name), so that lookups are not needed, and the plan will seek regardless of the stats around TYPEID. Plus, this index is useful even if you leave out INT109.