Well, this problem continues to perplex me, but I have a workaround. Unfortunately, though it works for now I don't know why this workaround is needed. I thought I'd detail what I tried and saw in case it helps someone else who is experiencing a similar issue.
On the suggestion of a helpful individual with wordpress support, I obtained the debug version of akismet. That keeps a log in /tmp/akismet.log. I edited the akismet.php file to log more detail than it was giving by default, and eventually found that akismet was having trouble connecting to the akismet servers after all. I was getting errno 11, "Resource temporarily unavailable" from the call to fsockopen. Increasing or decreasing the timeout length didn't help.
This made no sense to me because I tried a bunch of different ways of connecting to the akismet servers from the command line, and they all worked fine (lynx and telnet, for instance). nslookup had no problems looking up the IP addresses of these domains. But it looked like the call to fsockopen was timing out.
On a whim, I changed the fsockopen call in akismet.php, hardcoding the IP address of the server where the API key validation is done. Poof, the key validation suddenly worked fine. Then I put an entry for that server in /etc/hosts and changed the PHP file back to how it was originally, and that worked too. There is a second server akismet contacts (I suppose to get/send data about spam) which I also hardcoded into /etc/hosts. For the past day and a half or so all functions of the plugin are working fine.
This is obviously unsatisfactory because those IP addresses may change. But it works for now.
I find it bizarre. I don't understand what fsockopen is doing under the hood well enough to guess why it would successfully look up a domain name from /etc/hosts but fail to from DNS (I verified the nobody user has permission to do DNS lookups).
I saw a bug report for PHP 4.3 (which is what I'm stuck with, unfortunately) stating that fsockopen does not distinguish DNS lookup errors from other kinds of connection errors. So it seems like I'm not going to be able to get more detail about what's going wrong without working hard...
In any event, it looks to me like wordpress is doing what it should be doing, so I'll take this up with akismet. I think my problem is probably related to some issue on my server, maybe with this older version of PHP. Thanks to everyone who offered suggestions, I appreciate the help.