The box is still running PostgreSQL 8.1 and this started to increase a few weeks ago. It is only happening while the server is a bit busy.
fatal: pgsql:/etc/postfix/pgsql/relay_domains.cf(0,lock|fold_fix): table lookup problem
fatal: pgsql:/etc/postfix/pgsql/relay_domains.cf(0,lock|fold_fix): table lookup problem
fatal: pgsql:/etc/postfix/pgsql/relay_domains.cf(0,lock|fold_fix): table lookup problem
No other changes where made, so it seems to be related to a load increase. A new upgrade Debian Jessie box is in the works, but is there anything I can do in the meantime?
So this was all related to more load on the mail server. Upping the number of PostGreSQL connections in the config, solved this problem for me.