You may want to consider fun_plug'ing your 323 and then running avahi and netatalk. I have a mixed PC/Mac(Tiger, Leopard, and Snow Leopard) environment and all computers work well with the 323. My PC's connect via SMB. My Mac's all flawlessly connect via AFP. Time Machine evens works, too (with some additional manual setup -- lot's of info posted on the forums).
It is possible (although I am not an expert) that if you switched to connecting to the 323 via AFP, your delete issues might go away.