Again - Count(*) is overkill for a scenario like that. You don't care how many there are, you just want to know there are some matching records.

So instead of

select * from table1

where (select count(*) from table2 where table1.field1=table2.val1 and table1.field2=table2.val2) >0

Try using this (which usually runs faster)

select * from table1

where EXISTS (select top1 *from table2 where table1.field1=table2.val1 and table1.field2=table2.val2)

But still - this would run a LOT faster if you simply asked the owner of said DB to add in the index you need. Is this a vendor DB or something that prevents you from even asking?