Funny enough, I've encountered the same problem only once with an 871 Cisco router - after a power loss, the router lost its whole configuration - I was never able to explain it! When the customer brought the router to the office, I performed a quick check and saw everything seemed fine - no errors during post test.
As you did, I threw the backed up configuration and sent it back to the customer.
I'm suspecting that under very specific conditions the router's nvram looses its configuration, but I've got no further information or evidence to back this up.
I suppose we should always ensure we have a current configuration backup of all equipment we work with, as you never know what's going to hit you!