You can try disabling user and kernel level caching on your site. In IIS Manager > Output caching. That is where I would start by turning off one option at a time. Also, if you have some type of proxy server like ISA in front of your web server, it could cache the service. Lastly, verify the application itself doesn't have caching turned on.
Steve Schofield
Windows Server MVP - IIS
http://weblogs.asp.net/steveschofield
http://www.IISLogs.com
Log archival solution
Install, Configure, Forget