Unir fotografías

Todo depende de como se guarde la foto. Dado que el JPEG es un formato con perdidas, si no especificas una calidad suficiente puede resultar fácilmente en eso que dices.
Si tu programa de union no te permite especificar la calidad, cambiate a otro ;)
Si quieres uno bueno tengas que pagarlo, por ejemplo el Panorama Factory (http://www.panoramafactory.com/)

No se con que programa estas trabajando pero no es culpa del programa, efectivamente, todos trabajan así .La parte positiva es que, aunque es una manera de hacerlo, no estas "empalmando" de la mejor manera, no es fallo de nadie es culpa del desconocimiento, yo te explicaré como hacerlo bien.
Tus fotos cuando salen de la cámara tienen una resolución de 72 dpi, pues de lo que se trata es de "incrustarlas" en un nuevo archivo con más resolución y verás como funciona. Lo primero es crear un nuevo archivo en fondo blanco del tamaño que tu quieras y a 300dpi de resolución.(Si lo que te digo te suena a chino escríbeme a [email protected] y te aclaro cosas). Suele hacerse con el atajo ctrl+n... le das el ancho y alto del tamaño final que quieres para tú foto. Abres las fotos que vayas a unir y con la tecla de desplazar, (ctrl si trabajas con photoshop) arrastra la foto hasta el nuevo documento, haces lo mismo con la otra y las unes usando esa misma herramienta de desplazar.
Puede que no te ocupen toda la superficie del nuevo documento, se trataría de aumentar las fotos a tu conveniencia hasta que la resultante sea de tu agrado.
Una manera más sencilla y menos correcta es que de lo que tú haces y del resultado final que obtienes cuando empalmas fotos como lo haces es que vayas a la opción tamaño de imagen y cambies la resolución a 250-300 dpi, verás que el tamaño aumenta, el peso de la foto también, pero no es la mejor manera porque estas interpolando, el ordenador tiene un sistema para "inventando" información ampliar las imágenes, por eso no es la mejor manera. Si tienes dudas o no me he explicado bien ya sabes como contactar conmigo.