Now there's something you don't see every day...
I could hardly believe what I found when I opened up the server. One of the fans had been literally scotch-taped and rubber-banded in place! I'm not even sure why this was done, as all the necessary parts were there, the plastic mounting bracket just hadn't been snapped into its holes. The tape and rubber bands had actually failed, and the fan was flopping around loose in the case - lucky it didn't cause any damage. I re-installed the fan correctly, cleaned out the dust and debris, including a wad of lint that had wedged itself into the blades of the CPU fan, preventing it from spinning. Everything seems to be behaving now, not really any quieter than before because the fans are just getting old, but I don't think there is any cause for concern about overheating.
I recommended an upgrade/replacement, of course, but for their needs, they can probably get by quite a bit longer on this Linux box.