@Phil, @sean
You were spot on guys. Parameter sniffing was the culprit. I have 'fixed' it by assigning the parameters to local variables. This will work for me as this is a once a day extract query and performance is not critical as it happens overnight when the server load is quite low and the extract criteria are consistent (range from 1 to 3 days) and the data distribution is pretty even.
I also found the following good posts on parameter sniffing.
http://www.brentozar.com/archive/2013/06/the-elephant-and-the-mouse-or-parameter-sniffing-in-sql-server/[/url]
http://blogs.msdn.com/b/turgays/archive/2013/09/10/parameter-sniffing-problem-and-workarounds.aspx
NOTE: This is MY solution for MY problem, Do your own research! If you have high frequency queries or wildly different data distributions you may want a different solution
Aaron