You are right to be worried about this issue. Placing images that have already been converted to a specific CMYK profile in InDesign and then exporting to another profile is a common source of shifting colors. Or similarly, designing vector graphics in CMYK with the wrong profile and then changing the profile on export.
Background
A CMYK image is basically just a collection of pixels with each their CMYK values. They can have a color profile embedded (we say the image is "tagged" with that profile), but it's really just a name. The CMYK values have been determined when the image was converted. The profile doesn't do any additional trickery.
All print houses I've ever worked with (including our own) in the end don't really care about which color profile an image is tagged with. The CMYK values are used as they are as instructions to which halftone screens to burn to the printing plates. A 50% black simply becomes a 50% halftone screen on the plate. (There is also some calibration curve applied but that should be of no concern for a designer.)
Tagging PDFs and images is of course really helpful in the prepress phase where we check and preflight client PDFs and we of course care about which profile was used for the conversion. But if we receive an untagged PDF and the client assures us that they have used the correct profile and it seems to be correct, we can't start doing detective work on each and every image. We don't know how the RGB images looked like originally. We only see the resulting CMYK images. So if the CMYK values aren't obviously wrong (for example too high total ink or obviously wrong colors), we can't know if the image have been tagged with another profile than it was originally converted to.
A printing press is calibrated according to the color profile they recommend. The printer can't respect other profiles your PDF might have set as intent. And they certainly can't print different elements of your PDF with different profiles.
So using images with a wrong CMYK profile will introduce some uncertainty about the colors on print and should be avoided. Check out this example:
I've taken an image of a blue sky and converted it to PSO coated v3. The top part shows how it will look if printed according to PSO coated v3. The lower part shows how the same image looks if printed according to Coated FOGRA39. So there will be a difference (although in some cases you might not notice it).
Solution
In practice there are several ways to convert the images with PSO coated v3 to whatever profile the print house recommends.
Convert the images to Lab in Photoshop. That should be as lossless as possible and the images will convert to any CMYK profile on export like you are used to with RGB images when setting Output > Color > Color Conversion to Convert to Destination (Preserve Numbers).
Convert the images to the recommended CMYK profile in Photoshop. This also works with Output > Color > Color Conversion set to Convert to Destination (Preserve Numbers), but you have to save different versions of the images for different profiles.
Let InDesign handle the conversion. This is a bit tricky in my opinion and I must admit that I seldom use this approach. You need to make sure that each image has Object > Image Color Settings set to the actual profile of the image. This should happen automatically if you have set Edit > Color Settings > Color Management Policies > CMYK to Preserve Embedded Profiles, before opening the document and placing the images, but I've experienced some inconsistent behavior (perhaps it's just me messing it up). Now you should be able to export using Output > Color > Color Conversion set to Convert to Destination, but this requires that your document has the same color profile assigned as the one you export to. Otherwise your black and clean gray vector objects will be converted to all four CMYK inks.
About the proof issue
In the ideal world, every piece of equipment involved in the process is perfectly calibrated and follows a standard (including your monitor and the room or booth you view the printed material in). An image that has been converted from RGB to PSO coated v3 and printed according to that profile should look as similar as possible to the original you see on your calibrated monitor. And the same RGB image converted to some other profile (like Coated FOGRA39) and printed according to that profile should look almost identical.
In the real world, well stuff happens. If a print doesn't live up to your expectations the print house can easily blame your monitor or some random proof they receive from an unknown provider. In the end you are much better off letting the print house doing the actual print provide you with a proof. And to use the same images for both prints. That way it's their responsibility to make sure that there is likeness between the proof and the end result.
