Public key for xxx.rpm is not installed

After an upgrade to CentOS 5 / RHEL 5 we got the following error:

Downloading Packages:warning: rpmts_HdrFromFdno: Header V3 DSA signature: NOKEY, key ID e8562897Public key for openldap-2.3.27-8.el5_2.4.x86_64.rpm is not installed

It turns out that the key needs to be loaded and yum has not tried to load the key properly. The following manual key loading solved the issue:

rpm --import http://mirror.centos.org/centos/RPM-GPG-KEY-CentOS-5