PHP must be expecting to use the old MySQL authentication plugin algorithms. You do not have to restart mysql. Since old_passwords is a globally dynamic option, all you have to do is run the following:

SET GLOBAL old_passwords = 1;

In addition, please add this to /etc/my.cnf:

[mysqld]
old_passwords=1

to have future restarts retain this setting.

To further verify the need to do this, the next time you login to mysql, run this

SELECT LENGTH(password) password_length,COUNT(1) length_count
FROM mysql.user GROUP BY LENGTH(password);

If none of the passwords are of length 16, this may explain PHP's reluctance to login.

Sad to say, but the alternative would be to setup 16-character passwords, but you cannot reverse-engineer 41-character passwords. You would have to manually setup the 16-character passwords using the original plain-text values.

For example, if root@localhost had 'helloworld' as the password, it would have convert it using the OLD_PASSWORD function. Here is a comparison:

mysql> select password('helloworld');
+-------------------------------------------+
| password('helloworld')                    |
+-------------------------------------------+
| *D35DB127DB631E6E27C6B75E8D376B04F64FAF83 |
+-------------------------------------------+
1 row in set (0.00 sec)

mysql> select old_password('helloworld');
+----------------------------+
| old_password('helloworld') |
+----------------------------+
| 6c755a9e66debe8a           |
+----------------------------+
1 row in set (0.00 sec)

mysql>

Once you activate old_passwords, to convert it you would have to do something like this:

UPDATE mysql.user
SET password = OLD_PASSWORD('helloworld')
WHERE password = PASSWORD('helloworld');
FLUSH PRIVILEGES;

UPDATE 2013-02-02 22:44 EDT

If changing the authentication style on the MySQL side has not worked for you at this point, I have some bad news for you. You stated earlier:

I used php 5.2.9 and everything worked ok but lowering php is not a solution for me. I also have to mention that i dont have full access to DB's settings cause the client doesn't give me that full access.

You may need to downgrade PHP after all. If your hosting provider isn't in position or unwilling to adjust MySQL or give you a downgraded PHP, you will have to go with a hosting provider that will.

As an alternative you may want to look into Amazon EC2 when you can have full control of all software upgrades after running sudo -s. The links you mentioned before gave you what you needed to know. I gave you what you can do to accommodate the MySQL side. Do what you know has to be done to get this solved.

You should decide what exactly you need, before deciding those 3 options.

My suggestion is as following:

1. Install memcache and the necesary php module to use with memcache. Once you install memcache, you will have an IP and PORT to connect to, for SET / GET operations

2. Decide where exactly in your Wordpress php code you need to inject the code that displays the "featured" stuff

3. Add a php code similar to:

   • CONNECT to memcache
     
   • Check for the existance of a KEY/VALUE pair, named "FEATURED STUFF"
     
   • If there is, GET that pair, and display the pair's value
     
   • If not, run the SELECT query, FETCH the results, build a string that will contain the HTML body of "FEATURED STUFF", PUT the string in memcache as a KEY/VALUE pair.
     

4. The code above should not be cached with WP Super Cache. Let memcache do the cacheing for you.

If you need help with the actual implementation, let me know.

$memcache = new Memcache;
$memcache->connect('localhost', 11211) or die ("Could not connect");

if ($gotten = $memcache->get('featured_stuff')) {
    echo 'CACHE HIT'</br>';
    echo $gotten;
} else {
    # Never mind - fetch it and store for next time!
    $gotten = dbfetch($query, ...);
    $memcache->set($featured_stuff,$gotten);
    echo $gotten;
}