I'm fairly sure there is a global delete option in the 2004--if it is the same software level as the 2006, as I cleared my history when I sold a 2006. However, as I no longer have the car I only have my memory, so cannot give you any more detail, except to say keep looking and you should find it. Hopefully someone with a early Gen II with Nav will chime in.