PHP-MySQLi connection randomly fails with "Cannot assign requested address"

Since about 2 weeks I'm dealing with one of the weirdest problems in LAMP stack. Long story short randomly connection to MySQL server is failing with error message:

Warning:  mysqli::real_connect(): (HY000/2002): Cannot assign requested address in ..

The MySQL is on different "box", hosted at Rackspace Cloud Today we downgraded it's version to

Ver 14.14 Distrib 5.1.42, for debian-linux-gnu (x86_64).

The DB server is pretty busy dealing with Queries per second avg: 5327.957 according to it's status variable.

MySQL is in log-warnings=9 but no warring for connection refused are logged. Both site and gearman workers scripts fail with that error at let's say 1% probability. No server load DO NOT seems to be a factor as we monitor. (CPU load, IO load or MySQL load) The maximum DB connections (max_connections) are setted to 200 but we have never dealed with more than 100 simultaneous connections to the database

It happens with and without the firewall software.

I suspect TCP Networking problem rather than PHP/MySQL configurationn problem.

Can anyone give me clue how to find it?

UPDATE:

The connection code is:

$this->_mysqli = mysqli_init(); 
$this->_mysqli->options(MYSQLI_OPT_CONNECT_TIMEOUT, 120); 
$this->_mysqli->real_connect($dbHost,$dbUserName, $dbPassword, $dbName); 

if (!is_null($this->_mysqli->connect_error)) {
    $ping = $this->_mysqli->ping(); 

    if(!$ping){
        $error = 'HOST: {'.$dbHost.'};MESSAGE: '. $this->_mysqli->connect_error ."\n"; 
        DataStoreException::raiseHostUnreachable($error);
    }
}