The next thing to check is this...
so add this to your /etc/mysql/my.cnf files under the [mysqld] sections...
general_log = 1
general_log_file = /var/log/mysql/mysql.log
and tail -f /var/log/mysql/mysql.log while a message comes in/ What you are looking for is the EXACT mysql query which is defined in the mysql-virtual_recipient.cf file (cat the file to see it).
Once you see the log entry for, say, postmaster then ctrl-c out of tailing the log file and at the prompt type...
mysql -e "PASTE THE ENTIRE QUERY FROM THE MYSQL LOG FILE HERE;"
and that will either successfuly return a correct lookup... or give you an error as to why it failed, which could be as simple as the server_id field being wrong.