Thanks to everyone who has replied to my question. To answer some of the questions that have been raised:

- The default database isolation level is set to Read Committed

- No isolation level is being set in the stored proc

- No Lock is not used in the stored proc

So far I have tried adding in NOLOCK to the stored proc and this hasnt stopped the incorrect results on first run. I have also compared the exection plans between 1st and 2nd runs and they are both the same. I'm just going through the process of checking all the indexes are present and being rebuilt after the warehouse rebuild.

Thanks again

Mark