Hola de nuevo,
Al final he usado un programa llamado "Ultimate Paint" para convertir las imágenes de JPG a LBM, gracias a Alan_Smithee por la recomendación!

Lo que he hecho ha sido lo siguiente:
En primer lugar, siguiendo el consejo de na_th_an, le he dado a la imagen el tamaño correcto, tratando de achatarla un poco, con el fin de que el aspecto final en Deluxe Paint fuese el adecuado.
Después, he limitado la cantidad de colores de la imagen haciendo uso de la herramienta "Guardar para Web y Dispositivos" presente en el menú "Archivo" de Photoshop. Dependiendo del número de colores máximo que establezcamos, la imagen se asemejará a una paleta de colores CGA, EGA o VGA...maravilloso. Esta herramienta genera un archivo PNG.
Finalmente, convierto este PNG a Amiga IFF gracias al Ultimate Paint. Este formato es compatible con Deluxe Paint de PC y de Amiga, cosa que me interesa sobremanera, ya que dispongo de ambas máquinas. Lo único que tengo que hacer es renombrar la extensión IFF a LBM para que funcione en Deluxe Paint de PC.
La imagen final, aparece sin ningún tipo de espurio en el viejo Deluxe Paint 2 Enhanced, perfecta...

Un poco más de cerca!

Hay algo más chulo que un puto pixel?????
De nuevo, muchas gracias por la ayuda!
Un saludo a todos!