Thanks, Trev. Depending on whether others are suffering the same problem, it sounds as if either there's a glitch on the network somewhere or we're maybe still getting intermittent heavy load glitches.
I'll see if there's anything else we can do to lower the burden on the server - I remember seeing something somewhere about WP installations using a lot of resources to check whether it's time to publish scheduled posts. If it's that big a problem, someone must have come up with a workaround by now.