I've come across the first CD in my collection which does not have an entry in the CDDB or FreeDB. And the winner is...

Sandals, Feet Single, from their 1994 album "Rite to Silence."

UPDATE:

The very next CD I put in was also not in the database:

Deee-Lite, Picnic in the Summertime Single, from their 1994 album "Dewdrops in the Garden."