My first thought was that the report was using a cached version of the report, but that wouldn't be the behavior you are describing and it wouldn't explain why a direct call to the SP does the same thing.

I've never seen this happen on any version of SQL Server. Have you tried capturing the execution plan and seeing if it changes from run to run? That shouldn't cause incorrect results, and if it does I'd say you've found a serious bug.

What is the isolation level used?