Thanks Woolfgang. Yep, we totally own all the appropriate rights. In fact, the book has actually been in print for some time now. We're just trying to do it again for the e-book version. But yes, 'all rights reserved' I *think* is the legally accurate term.
An image is pixelated because it doesn't have the information in any more detail. No program no matter how good can get the information that is not in the image.
Many programs will "interpolate". They insert pixels of an intermediate colour and brightness between the pixels that are there but it will not bring back the detail that was in the original scene. It doesn't really improve the resolution, just increase the pixel count.
Some might even look around the pixel and guess that a straight line approaching it should actually continue through. These can potentially help but unlikely without a lot of human intervention.
The new designer will paint over the original in higher resolution and recreate an impression of what they think should be there. It is really the only way you will get a satisfactory outcome if you need to increase the size of the image beyond what the original pixels will support.