As Jonathan and Chris have answered the one and only way to achieve a better print quality is to start from bigger image.
Technically all certificate functions that print graphic elements call the very same TCPDF (the library used by the certificate module to generate the pdf) function.
This function takes 4 main arguments x, y, w, h
x and y define the place of the element on the page
w and h define the dimensions of the element.
To show you the importance of resolution and that a better quality is quite possible I did a small test. I downloaded a very big Moodle logo somewhere on a forum, then in Photoshop I made 2 differents copies
moodle-logo1.jpg is 150 x 31 pixels so 5,36 cm x 1,11 cm at a 71 dpi (dot per inch) resolution (equivalent to 28 dots per cm) and the file size is 14,3 Ko
moodle-logo2.jpg is 633 x 131 pixels so 5,36 cm x 1,11 cm at a 300 dpi resolution and the file size is 38,3 ko (please note that the resolution and filesize are bigger but the dimensions are the same !)
Then rather than including these 2 elements in a certificate I wrote a little test script to generate a pdf using the TCPDF library
The lines used to generate the 2 images are
$pdf->Image('moodle-logo1.jpg', 15, 40,53,11);
$pdf->Image('moodle-logo2.jpg', 15, 70,53,11);
All units are in millimeters so the first image is at 15mm from left and 40 mm from top and dimensions are 53 mm by 11 mm
The second image is at the same distance from left, 30 mm under the first and have the same dimensions.
As you will see screen display at 100% is nearly the same (so you don't need to have any worries about screen display) but printing wil reveal quite a difference in quality.
I hope this will help some certificate users.
I attach the 2 images and the resulting pdf document.
PS currently (with the certificate for Moodle 2.0 version that I donwloaded a few days ago) this works for all graphic elements BUT the signature. Chadelle would need to change a few lines of code so that this resolution trick also works for signature.