I tried deleting, then setting up replication again"
Do you mean you deleted the local replica of the mail file, and re-created it? How did you delete the database? And did you delete Cache.ndk? I don't know if this would affect your situation, but I've been told its a good thing to do when problems re-appear.
If it only happens on the local copy, then its likely its simply a corrupt replica, but if this is the case then deleting and recreating the replica should fix the problem, which leads me to question your methods. Did you use the "Database -> Delete" command on the workspace tab? I've also been told that deleting nsf files with Windows Explorer is not a good idea, especially when Notes is running.
Sorry I can't be more concrete help, but if I could solve your problem instantly, then I'd be on a higher salary. All I can do is spread the wealth!
Good luck!