The situation:
  1. Anonymous user clicks on link to node/1234 (recently created) and gets "page not found"
  2. Link works for logged in users.
  3. Clear cache
  4. Link now works for anonymous users
  5. Note: there is no "page not found" error written to Watchdog
This is on a D5 install.

This makes no sense to me.

Is Drupal caching the non-existence of pages?

Isn't it supposed to work like this for anon users: URL is called, Drupal checks to see if there is a cached version. If there is, it gets the cached version, if not, it runs the queries and builds the page from scratch.

Thanks for solving this mystery,

Shai