I also have experienced these same issues and have tried the same solutions to no avail.
I have had new messages that appear in my server mail file Inbox, replicate to my local copy yet they do not appear on my local Inbox. They also do not appear in any View including All Documents. However, if I do a Search on my local mail file the messages appear.
I have also deleted messages from my Inbox yet they remain visible in the Folder. If you try deleting them again an error is displayed indicating that the Document is gone; I think the actual error is Object not set or something. The deleted docs are present in they Trash folder, as expected and can be restored.
Is there a reliable fix or solution for this? I am running the 8.0.1 client.
This problem has not occurred for me again since installing release 8.0.2. Therefore, either the problem seems to be resolved in release 8.0.2 or there was an issue with my installation of 8.0.1 and the re-install of 8.0.2 resolved it. I will keep my eye on it.