Various errors with online repositories

Trying to update Ubuntu 12.04.2 with the latest releases I see various errors executing "apt-get update".

It did not help, as expected by many, to remove the package lists from /var/lib/apt/lists/* and /var/lib/apt/lists/partial/* with "rm -vf /var/lib/apt/lists/* and /var/lib/apt/lists/partial/*". Same errors again (see attached log).

I've tried with ubuntu.com and de.ubuntu.com -- same errors at the very same places/files. Maybe these are corrupted on the servers already??

Additionally an error occured trying to fetch the ubuntu-extras signing key:
# apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 16126D3A3E5C1192
Executing: gpg --ignore-time-conflict --no-options --no-default-keyring --secret-keyring /tmp/tmp.0te6zdsmhW --trustdb-name /etc/apt/trustdb.gpg --keyring /etc/apt/trusted.gpg --primary-keyring /etc/apt/trusted.gpg --keyserver keyserver.ubuntu.com --recv-keys 16126D3A3E5C1192
gpg: Schlüssel 3E5C1192 von hkp-Server keyserver.ubuntu.com anfordern
gpgkeys: key 16126D3A3E5C1192 not found on keyserver
gpg: Keine gültigen OpenPGP-Daten gefunden.
gpg: Anzahl insgesamt bearbeiteter Schlüssel: 0

ProblemType: Bug
DistroRelease: Ubuntu 12.04
Package: apt 0.8.16~exp12ubuntu10.10
ProcVersionSignature: Ubuntu 3.2.0-40.64-generic 3.2.40
Uname: Linux 3.2.0-40-generic x86_64
ApportVersion: 2.0.1-0ubuntu17.2
Architecture: amd64
Date: Thu May 23 09:45:52 2013
InstallationMedia: Ubuntu-Server 12.04.1 LTS "Precise Pangolin" - Release amd64 (20120817.3)
MarkForUpload: True
ProcEnviron:
 TERM=screen-bce
 PATH=(custom, no user)
 LANG=de_DE.UTF-8
 SHELL=/bin/bash
SourcePackage: apt
UpgradeStatus: No upgrade log present (probably fresh install)