What they are telling you is the aspect is wrong. For example if your image is has a 600px width and 400px height it has a 6:4 aspect. Since the print medium is 6:4 it will fit perfectly.
What your issue is consumer digital cameras create 4:3 images. As an example if your images are 650px wide and 400px high they have an aspect of 6.5:4 . If you resize the image to 600px wide and 400px high you'll have the correct aspect for the print paper HOWEVER the image is now going to be skewed. e.g balls will take on a slight egg shape. That's why they won't print it as you have sent it to them, they are actually doing you a favor because most places will either skew the image or crop it. Cropping manually introduces issues you might be cropping off heads etc.
To get the right aspect you need to crop it yourself. Irfanview unfortunately does not do this in batch mode except by coordinates but you can do it with a single image by ratio. Open the image, then click edit>create custom crop selection . Choose 3:2 which is the same as 6:4.
Hit ctrl and drag the selection box so at least one side goes fully across the image. You can move the selection box by right clicking it however make sure you do not reposition it outside the image. Then click edit>crop selection. Save the file using "save as" to crete new file and send to printer.
You can do this in batch mode if you know what the amount of pixels you need to crop are. You can base it on the image you just created. For example if you're resultant image is 600px by 400px and the original is 650px by 400px set the coordinte to cropp 25 px off the top and 25px off the bottom.