Are you by any chance using special characters, such as accents?
Did you try to change the encoding of the server by using the .htaccess file?
php_value default_charset UTF-8
AddDefaultCharset UTF-8
Try replacing UTF-8 with iso-8859-1 or iso-8859-2.
EDIT: Are you posting double spaces? WordPress interprets these (in rare occasions) as a forced space, a non-breaking space (nbsp). Did you notice any pattern of deletion by using ampersands or other special characters?
Did you try to deactivate all plugins and set the default theme?