Hi Sergei;

My environment is:
  * openindiana (OI, solaris) dekstop, mysql clients: 5.5.20 and 5.6.4-m7 (from dev.mysql.com)
  * VirtualBox guest: centos x86_64 desktop, mysql client 5.5.21 (from dev.mysql.com)
  * OpenVZ guest, centos x86_64 server, mysql 5.5.23 (also   from dev.mysql.com)

  * kerberos 5 is enabled (using LDAP as backend) if that matters (i don't think so).

Answers:
1) Tried all variants (plugin downloaded from http://www.percona.com/downloads/Percona-PAM-plugin/0.1/)
  a) binary, x86_64 rpm for centos 6 
  b) self compiled, also on VBox guest x86_64 centos 6.2, with ./configure --prefix=%{_libdir}/mysql/plugin --disable-static (have created spec file, MySQL-devel and pam-devel deployed)

2) no. i got no impression that i have to do it (at least from documentation available on http://www.percona.com/doc/percona-pam-for-mysql/index.html page). But, we can ignore OI for moment.

3) Users are created this way:
INSTALL PLUGIN auth_pam_server SONAME 'auth_pam.so';

CREATE USER 'micro'@'localhost' IDENTIFIED WITH auth_pam_server;
CREATE USER 'micro'@'predrag-ovz%' IDENTIFIED WITH auth_pam_server;
CREATE USER 'micro'@'solarix%' IDENTIFIED WITH auth_pam_server;
CREATE USER 'micro'@'predrag%' IDENTIFIED WITH auth_pam_server;
CREATE USER 'micro'@'predrag-skype%' IDENTIFIED WITH auth_pam_server;
CREATE USER 'micro'@'predrag-skype.my-domain.com' IDENTIFIED WITH auth_pam_server;
GRANT ALL PRIVILEGES ON *.* TO 'micro'@'predrag-skype%' IDENTIFIED by auth_pam;
GRANT ALL PRIVILEGES ON *.* TO 'micro'@'predrag-skype.my-domain.com' ;

User micro is, in LDAP, defined under ou=People,dc=my-domain,dc=com

4) cat /etc/pam.d/mysqld 
auth       required     pam_warn.so
auth       required     pam_unix.so audit
account    required     pam_unix.so audit

5) That is exactly problem. I cannot establish connection using PAM.
  a) centos desktop -> centos server:
    mysql -hpredrag-ovz -umicro  -e "select now()"
Password:
ERROR 1698 (28000): Access denied for user 'micro'@'predrag-skype.my-domain.com'

   centos-srv:/var/log/sercure (debug enabled in /etc/pam_ldap.conf)
Apr 26 08:56:10 predrag-ovz mysqld: pam_warn(mysqld:auth): function=[pam_sm_authenticate] service=[mysqld] terminal=[<unknown>] user=[micro] ruser=[micro] rhost=[predrag-skype.my-domain.com]
Apr 26 08:56:18 predrag-ovz mysqld: pam_unix(mysqld:auth): authentication failure; logname= uid=101 euid=101 tty= ruser=micro rhost=predrag-skype.my-domain.com  user=micro
 
  b) everything on centos server
   mysql -hpredrag-ovz -umicro  -NBe "select now()"
2012-04-26 09:02:22
  ## That do not ask for password at all ? ##
  
   mysql  -umicro  -NBe "select now()"
Password: 
ERROR 2013 (HY000): Lost connection to MySQL server at 'sending authentication information', system error: 32

   /var/log/secure
Apr 26 09:03:26 predrag-ovz mysqld: pam_unix(mysqld:auth): conversation failed
Apr 26 09:03:26 predrag-ovz mysqld: pam_unix(mysqld:auth): unable to obtain a password
Apr 26 09:03:26 predrag-ovz mysqld: pam_unix(mysqld:auth): auth could not identify password for [micro]

  I have double checked: password i am using is saved in LDAP and i can connect to using openldap tools. Also, i am doing copy-paste of it (no typing).

Any clue?

I still thing that there is something wrong in approach: why do i need to use plugin on client side at all?

Bast regards.