Do you call FNNotify after moving files? I know pre-Tiger Finders would fall behind if you omit that step.

If it was Tiger, then it definitely should have noticed anyway. (However, not FNNotifying will still confuse the Dock if you move things to the Trash.)