>>Проверь в конце концов, правильность записи для localhost в /etc/hosts
Проверил, в порядке

>mysql -u user -p -h localhost mail
Проверил пускает,
>сделать под root-ом MySQL

ВКлючил лог запросов. У меня Exim юзеров берет из той же базы без проблем. А вот authdaemon не может аутентифицироваться нормально,  
060316 22:05:55       5 Connect     exim@localhost on mail
                      5 Query       SELECT domain FROM domains WHERE domain='test.com' AND (type='LOCAL' OR type='VIRTUAL')
                      5 Query       SELECT recipients FROM aliases WHERE local_part='user' AND domain='test.com'
                      5 Query       SELECT recipients FROM userforward WHERE local_part='user' AND domain='celticdance.ru'
                      5 Query       SELECT home FROM users WHERE id='user' AND mbox_host='test.com' AND active='Y'
                      5 Quit      
                      6 Connect     exim@localhost on mail
                      6 Query       SELECT quota FROM users WHERE id='user' AND mbox_host='test.com'
                      6 Query       SELECT CONCAT(home, "/Maildir") FROM users WHERE id='user' AND mbox_host='celticdance.ru'
                      6 Quit      
060316 22:07:45       7 Connect     Access denied for user 'exim'@'localhost' (using password: YES)
060316 22:09:11       8 Connect     Access denied for user ''exim''@'localhost' (using password: YES)

чтото меня пугают кавычки 'exim'@'localhost' , может у меня то нетак с запросом ?

MYSQL_SERVER            127.0.0.1
MYSQL_USERNAME          exim
MYSQL_PASSWORD          stribog
MYSQL_SOCKET            /tmp/mysql.sock            
#MYSQL_PORT             3306
MYSQL_OPT               0
MYSQL_DATABASE          mail
MYSQL_SELECT_CLAUSE     SELECT CONCAT(id,'@',mbox_host), crypt, "", 1001, 6, home, CONCAT(home,'/Maildir'), "", id, ""  FROM users WHERE CONCAT(id,'@', mbox_host) = '$(local_part)@$(domain)'