It certainly wasn't the refbacks causing it IMO. There's no chance that by removing content, that it would remove any penalty you may have within 24hours. Google doesn't work that fast. What is more likely is the algorithms were being changed, or you were using a different datacenter on your two searches. I was searching for something at work yesterday on a keyword, and found what I wanted. I came home, and searched again and it was giving me different results
Btw you shouldn't get search engine results in the refbacks, and if you do it's probably from a non-standard search engine, which you should add to the blacklist

I will be adding regex support to my mod soon, so that'll make it a lot easier for me to ban every google domain, and any other search engines I can think of