We've worked with a client on this and even moved it to mysql2 for a test, with no improvement for them, so I don't think this is MySQL4 issue we are checking some other things as well.
The server that is connecting for you, is it web5? We are trying to find any commonality.