First thing you may want to do is compare the actual execution plans for the query from each run. See if there are any differences there. You may want to post those here as well, just save them as .sqlplan files and attach them to a post.