Thanks guys, I really appreciate your effort. Joachim, you advice " to save the images with a image editor that "corrects" the orientation" has worked, thank you for the tip! Until the bug in AP is fixed, I can at least work on my projects, hurray!
EDIT: One more thing that might (?) be connected with the same problem: When I prepare my master pages and move the picture frames, e.g. I have 4 vertical picture frames in one row and 3 horizontal picture frames in one row below the vertical ones, and swap the rows by using the Flip vertical tool, so that the horizontal picture frames are above the vertical ones: when I place images in the frames, they are flipped inside the frames. I understand the need to flip images or icons or whatever, however flipping picture frames in my opinion should not influence the placed image, as one can flip the placed image on its own (which is possible right now in AP).
Making progress here, having same problem with the original images. Reading the EXIF 0302, 0305, 2120 have an orientation Right top and 0315 has an orientation of Left bottom. Next step for me was opening the files in Photoshop / APhoto and saving them as JPEG again. The EXIF gives now the orientation of Top left regardless being portrait or landscape.
A wild shot in the dark: Publisher computes the image orientation upon the EXIF information "Orientation" and gets confused about Right top and Left bottom. Unless this is fixed I recommend you to save the images with a image editor that "corrects" the orientation.
EDIT: I am too slow, thx Carl for additional information.