This page (http://www.postfix.org/ADDRESS_VERIFICATION_README.html)
looks like it describes part of your problem. Could be the solution
Regards
tobi
I had had a lot of troubles with verification database. For example...
new customer is added to SMTP relay, changed MX record to point my
server, but end user misconfigured something on the server for
example... user john wasn't configured and after a couple of days it
turned out "john" is missing. So John was added to the remote server,
run some tests and what ? My server still says "No such user" why ?
Because it remembers that in the database. After that I have had to
remove the database and restart daemon, finally I completely got rid of
verify.db and did verification without db.
Regards,
Jarek