MySQL stops authenticating remote connections

[Daniel Nichter]

I have a very weird problem with MySQL 4.0.22 where it stops authenticating remote connections. Eventually MySQL reaches max_connections and it has to be restarted. Sometimes it restarts nicely, sometimes it wont and it has to be killed. Here's what I've done to isolate the problem to MySQL:
1. Local connections always work so MySQL isn't frozen
2. Any remote server is effected, so it's not MySQL blocking one particular IP
3. Any remote script is effected, so it's not a particular PHP or Perl issue
4. No query is frozen. I enabled general logging and every time every connection ID quits nicely, then there is a large gap of no queries, no connections.
5. Any db or table is effected
6. The network is ok because I never lose SSH or ping connectivity
7. In the priv table it doesn't matter if it's allowed by IP or domain--either fail
8. Full process list shows *nothing* but:
Id: 1858
User: unauthenticated user
Host: 1.2.3.4:51568
db: NULL
Command: Connect
Time: NULL
State: login
Info: NULL
9. Any MySQL user is effect. I created a new user: It won't authenticate either
10. MySQL is the only thing running on this server--No firewall, no floodguard, no IDS, etc.
11. Server load, queries/second are all very low and neither shows any relation to the issue

All indication point to MySQL just dropping dead for remote connection auth. Possibly a bug?