First of all thanks!

when I imported the images, Xara gave me the option of lowering the resolution or keep the original (with a large filesize warning or something like that).
I chose "Keep Original Resolution" at all times, because that's just what I wanted.
So this should be what you mentioned Albacore?

Once again, on the screen it looks fine to me and good to print.
I exported the whole thing now with 600dpi and let them check again.

@SignPig: I absolutely understand that. But resolution ist relative to the actual printsize. So if I have an image that is 30cm wide in 96dpi, it will have 9,6cm in 300dpi, without changing any pixels.
Some of the images were lower dpi, but I shrunk them way down while at the same time giving them more dpi. (In Photoshop: Image -> Image Size, set resolution from 96dpi to 300dpi with "Resample Image" UNchecked does exactly that).