Then, the next time I fired up PSE, the strange thing happened: All the previews were there, but as soon as I wanted to open it, PSE reported like "can not find media".
Soon I discovered that, when i select a picture, it showed the wrong drive letter. The remainder of the path, as well as the filename, was correct, strange!
Now, I checked what happens upon import. To do this, is created a new catalog and imported some pictures. This all went well and the path and drive letter was correct, i could even open the images and edit them. However, after closing and restarting PSE, the drive letter was wrong again, E: instead of D:. Clearly PSE was doing something wrong.
After some research on Google, I found users describing similar issues. It seems PSE uses primarily the volume-ID for its drive information rather than the drive letter. This makes sense regarding the problem when connecting multiple external drive to a PC and possibly get different drive letters.
So i checked the volume-ID of my D: and E: drives using the vol d: command.
And traraa: Both, the D: as well as the E: drive indicated the same volume-ID.
And now it dawned on me: Some time ago these two drives were part of a RAID1 configuration. In the meantime I use them independently, but obviously the still share the same volume-ID.
To solve the problem I simply used the Sysinternal tool volumeid to change the volume-ID of one of the two drives. For a good explanation on this see here:
http://www.wintips.org/how-to-change-hard-disks-volume-serial-number-volume-id
After this, I again created a new catalog, imported all pictures, and now the drive letter remains and everything works fine.