The problem had nothing to do with permissions!
The problem is that WinXP does not share drive mappings among different logons. So a mapped drive created by user X is not visible to the services. See
http://msdn.microsoft.com/library/de...ted_drives.asp
for more info.

I ended up mapping the drives using WNetAddConnection2() in my service, and now it's happy (and so am I!!).