Christo, lucky for you that you are in newsprint - this is a very forgiving medium for less than ideal originals.
Your output is probably 85 or 100 lpi - so with the golden rule of around 1.5 to 2 x the input pixels as output lpi you will need around 130-200 ppi in the image when used at 100% size.
So, when you first get the image/s - crop a dupe down to the approx content reqd. Go to image/image size and uncheck the resample box so that no new pixels are added or existing pixels removed. Resize the ppi to 130-200 ppi as your tests have indicated whatever figure works best for this type of image content. The print size of the image will grow/shrink to accomodate the new resolution ppi size that you have entered. This is now the largest size that you can place and use this image without inventing new pixels (upsampling).
Get the folk taking the pics to use the largest resolution they can. If this is not enough then they need a better camera or you have to invent pixels.
Get the folk taking the pics to use less JPEG compression, and to buy more cards to write the higher res files to.
For cleaning up digicam images, I would recommend this action set:
http://www.2morrow.dk/75ppi/coolpix/actions/
Regards,
Stephen Marsh.