Node_loads can fail if the user doesn't exist in the users table. Node_load does a INNER JOIN users ON u.uid = n.uid. That will fail if the users.uid doesn't exist anymore (i.e. user is deleted by hand). Don't know if that is the case for you but something along those lines maybe.

The node access rebuild can be a little sensitive: http://drupal.org/node/478946


Message: 2
Date: Wed, 3 Mar 2010 11:22:53 +0100
From: Llu?s <enboig@gmail.com>
Subject: [development] ghost nodes
To: Drupal Development <development@drupal.org>
Message-ID:
       <45a29f451003030222j13023250ta2284b2a16a8eed2@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1

I am developing an access module and when rebuilding my node_access
table some nodes don't get rebuild. I don't know the cause but when
trying to analyse them with devel access node module I have discovered
that some of them are valid and some other show me the "page not
found" message.
So all of this have raised me 2 questions:
- ghost nodes: why nodes which are in {node} and {node_revisions} show
me a "page not found" message; is there any other table? how can I
track this?
- Why some nodes which get correct $grants when displaying them; don't
get them saved when rebuilding permission table?

Any hint is welcome. I ask both things together because I think they
may be related as I am working with custom nodes hardcoded by myself.

--
*Les normes hi s?n perqu? hi pensis abans de saltar-te-les
*La vida ?s com una taronja, qu? esperes a exprimir-la?
*Si creus que l'educaci? ?s cara, prova la ignor?ncia.
*La vida ?s com una moneda, la pots gastar en el que vulguis per?
nom?s una vegada.
*Abans d'imprimir aquest missatge, pensa en el medi ambient.