Oh, you neglected to mention that it was a vendor database. Key piece of information.

having said that, the only way I can think of helping this situation out is to create a table in another database (that you control) and then indexing the columns... and then you'd have to modify the query... if you can't do that, I have no idea how to fix it.