Instalei o PHP 4 com um MySQL 5 no windows para efetuar alguns testes. Ao criar um script simples para conectar no MySQL foi apresentada a seguinte mensagem:

Client does not support authentication protocol requested by server; consider upgrading MySQL client

Após algumas consultas descobri que é só re-definir a senha do usuário que está acessando o BD, uma vez que o cliente MySQL do PHP utilizado na versão 4 é um pouco antigo. Para isso é só executar o comando:

mysql> SET PASSWORD FOR 'usuario'@'servidor'= OLD_PASSWORD('novaSenha');

Referência: http://dev.mysql.com/doc/refman/5.0/en/old-client.html