I just had the following scenario when trying to install openvpn:

Step 1: installing openvpn fails due to an authentication problem

# apt-get install openvpn
Paketlisten werden gelesen... Fertig
Abhängigkeitsbaum wird aufgebaut... Fertig
Die folgenden NEUEN Pakete werden installiert:
  openvpn
0 aktualisiert, 1 neu installiert, 0 zu entfernen und 0 nicht aktualisiert.
Es müssen 338kB Archive geholt werden.
Nach dem Auspacken werden 918kB Plattenplatz zusätzlich benutzt.
WARNUNG: Die folgenden Pakete können nicht authentifiziert werden!
  openvpn
Diese Pakete ohne Überprüfung installieren [j/N]? n
E: Einige Pakete konnten nicht authentifiziert werden

Step 2: list the keys we use on the system

# apt-key list
/etc/apt/trusted.gpg
--------------------
pub   1024D/2D230C5F 2006-01-03 [expired: 2007-02-07]
uid                  Debian Archive Automatic Signing Key (2006) 

pub   1024D/6070D3A1 2006-11-20 [expires: 2009-07-01]
uid                  Debian Archive Automatic Signing Key (4.0/etch) 

pub   1024D/ADB11277 2006-09-17
uid                  Etch Stable Release Key 
...

Step 3: make sure it is not a missing debian-archive-keyring

# apt-get install debian-archive-keyring
Paketlisten werden gelesen... Fertig
Abhängigkeitsbaum wird aufgebaut... Fertig
debian-archive-keyring ist schon die neueste Version.
0 aktualisiert, 0 neu installiert, 0 zu entfernen und 0 nicht aktualisiert.

Step 4: get the key as described here

# gpg --keyserver pgpkeys.mit.edu --recv-key 6070D3A1
gpg: requesting key 6070D3A1 from hkp server pgpkeys.mit.edu
gpg: key 6070D3A1: public key "Debian Archive Automatic Signing Key (4.0/etch) " imported
gpg: no ultimately trusted keys found
gpg: Total number processed: 1
gpg:               imported: 1

Step 5: import the key as described in the same document

# gpg -a --export 6070D3A1 | apt-key add -
OK

Step 6: again list the keys

# apt-key list
/etc/apt/trusted.gpg
--------------------
pub   1024D/2D230C5F 2006-01-03 [expired: 2007-02-07]
uid                  Debian Archive Automatic Signing Key (2006) 

pub   1024D/6070D3A1 2006-11-20 [expires: 2009-07-01]
uid                  Debian Archive Automatic Signing Key (4.0/etch) 

pub   1024D/ADB11277 2006-09-17
uid                  Etch Stable Release Key 
...

Step 7: Be stupid enough to try again to install openvpn package

# apt-get install openvpn
Paketlisten werden gelesen... Fertig
Abhängigkeitsbaum wird aufgebaut... Fertig
Die folgenden NEUEN Pakete werden installiert:
  openvpn
0 aktualisiert, 1 neu installiert, 0 zu entfernen und 0 nicht aktualisiert.
Es müssen 338kB Archive geholt werden.
Nach dem Auspacken werden 918kB Plattenplatz zusätzlich benutzt.
Hole:1 http://ftp.de.debian.org etch/main openvpn 2.0.9-4etch1 [338kB]
Es wurden 338kB in 0s geholt (392kB/s)
Vorkonfiguration der Pakete ...
Wähle vormals abgewähltes Paket openvpn.
(Lese Datenbank ... 166333 Dateien und Verzeichnisse sind derzeit installiert.)
Entpacke openvpn (aus .../openvpn_2.0.9-4etch1_i386.deb) ...
Richte openvpn ein (2.0.9-4etch1) ...
Starting virtual private network daemon:.

Why was this successful ??

In a nice little world the imported key should not have changed at all. Hmm, I did not check the fingerprint before and after. But reimporting the same key should have given the same error as in step 1. But that was not the case. Why not? What happened?

I really have no explanation. If there are good reasons the system behaves like this please give me a hint.

And yes. I used apt-get update to update the package list before all this happened!

The fingerprint of key A70DAF536070D3A1 after this happened is:
A999 51DA F9BB 569B DB50 AD90 A70D AF53 6070 D3A1