I ran into something similar when my search had a criteria that contained a date/time. I believe I had Leads created since 12:00PM Yesterday. When I viewed it in the UI, I got one set of results, when I called it in a script, I got a different set. It essentially stripped the time part out of the criteria. Not sure if this is related