I am experiencing the same exact problem. Takes about 45 seconds for the first query and then all subsequent queries run right away. I am running sp1, so I don't...

If I understand your question correctly I think this will give you what you want. Apply the criteria if there is any otherwise give you all the records.