Why doesn't Airport reconnect after sleep or shutdown?

The problem got partially better on its own, and it's not clear why. There were also a lot of old networks in the list of previous wifi networks in System Preferences, and it helped to delete them.

The complete fix, however, ended up being to go into the list of wireless networks (in System Preferences > Networks > Airport, Advanced) and move the desired network up to the top of the list so it was joined first. There was one called "linksys" on top that was matching a neighbor's network, and then failing to get internet access for some reason; I think it was added a long time ago for a different network of the same name.

I thought I had tried this before, but either something changed or I didn't actually try it. I'm asking this question to help me troubleshoot someone else's computer, so I'm not aware of everything that might have changed since I originally posted the question.

There is one famous cause of this problem - interference between bluetooth and wifi, which plagues metal Mac laptops.

To test if this is the source of your problems, turn off your Bluetooth via System Preferences / Bluetooth and see if the issue goes away.

If this is indeed the problem, the only cure (as far as I know) is to stop using Bluetooth entirely, or switch the frequency of your wireless setup to 5GHz.