Vista and Windows Explorer weirdness

I have two computers--one upgraded from XP to Vista Business and one with XP,
SP2 connected to a Linksys router. Both machines are up to date on patches. I
shared drives and folders on each machine and put them both in a workgroup
called (creatively enough) WORKGROUP. Each machine can see the other and
access the other.

The problem: If I delete a file or folder on the XP machine FROM the XP
machine, Vista doesn't really recognize it as deleted--it leaves the file or
folder visible in Windows Explorer when I use WE on the Vista machine to view
the XP machine. The deleted files and folders have a gray X for their icon.

On the other hand, if I delete a file or folder on the XP machine FROM the
Vista machine, the Vista machine (and the XP machine) both know it's gone.

I've tried all the obvious things--F5 on the Vista machine, booting clean,
booting in Safe Mode...the Recycle Bin gets emptied every day, sometimes many
times each day.

On the Vista machine, I don't use Shadow Copy or Synchronization (although I
think I accidentally synchronized once before I shut it off.

Any ideas on how to get the Vista machine to notice and "update" properly
(by not displaying deleted items) when I delete files or folders on the XP
machine?