This has been reported a number of times over the years, but the root cause has never been really identified. The one thing which seems to be clear is that it is caused when a schema is dropped but some references to it are not. There is evidence that at least in some cases this is a "special" schema created for a user's temporary tables.
The traditional fix is to log in as a database superuser and delete the lingering references to the schema from system tables. pg_depend and pg_type seem to be the main tables where these are found. Some people prefer to create a schema and update its oid to match the missing schema and poke around first, but I haven't seen that yield much additional information or recover any data.
This may not be related, but it may be a clue: I concerned by the statement that you
VACUUM FULL ANALYZE whenever you do anything major. What version is this? Do you run that against the whole database, or just specific tables? Do you REINDEX afterward? Generally VACUUM FULL should be considered to be a very aggressive form of maintenance which should only be needed if there was some problem.
If you feel that you have evidence of what caused the problem, please share with the PostgreSQL community so that we can get it fixed. So far nobody has produced a reproducible test case or provided enough forensic evidence to track it down, and it has been infrequent enough to be hard to catch. You could start with an email to email@example.com if you have some evidence.