Thanks for the speedy replies:
Gord - checked the Admin module but the option you mention is not listed.
Rooster - Not the cause of the problem, sorry to say. I can see some notes of the type the user has lost so I know it's not the 'show all/logged notes' setting.
Bit more info: I checked the database via ODBC connection and also the Pervasive Control Centre and I can see the gap in sequence number for the one contact I'm focusing on, so I know the note was there. Also, the user has a hard copy of the note to prove this. Strange thing is that the note isn't on any of the remote databases so it's like a delete event have occurred (ie: Maxexchange has somehow thought the notes needed to be deleted from ALL databases where it exists). However, I do not believe that a user has made the deletion as the missing notes are critical so it makes no sense at all for somebody to delete them.
There was a similar problem last year with clients being deleted by the software under certain scenarios. We ran nTH tier then and moved to a 2-tier structure and that made the problem go away, or at least we stopped seeing clients being deleted - they just get withdrawn from remote databases now.