1) .. Ahí estás en el dilema de siempre: tiempo proceso vs espacio en disco.
Por supuesto que si en el proceso de "upload" de esas imagenes tu le aplicas tu proceso de generación de tus "thumbs" .. optimizas la ejecución de tus scripts .. pues ese proceso lo harás una vez (cuando suba la imagen o se modifique).
La decisión de que método usar: generar el thumb como archivo o bien mostrarlo en línea (generado en tiempo real al vuelo ..) depende de tu aplicación. Si tu no vas a ofrecer a tu usuario la posibilidad de crear esos Thumb's con las dimensiones que quiera .. y son fijos, usa la primera opción: genera el thumb como archivo. Si el usuario podría tener la opción de personalizar esa generación de la imagen .. ahí es necesario generarlo al vuelo,
La generación del Thumbnail se hace en el mismo script que tu procesas el Upload del archivo (por qué supongo que tendras un formulario HTML para tal fin? .. o las suben por "FTP" las imagenes? ..)
Todas las funciones de tratamiento de imagenes (en GD por ejemplo:
www.php.net/gd) tienen un parámetro para indicar que generas un archivo (y en que ruta con el nombre que gustes .. por ejemplo algo como thumb_nombrOriginal.tal)
Si buscas en el foro por "thumbnails" veras muchos ejemplos de funciones para crearlos, también en las FAQ's del foro PHP y en sitios como
www.phpclasses.org y por supuesto en la documentación oficial de PHP sobre funciones de tratamiento de imagenes GD:
www.php.net/gd
2) .. Deberías usar un identificador "único" y aleatorio en lo posible, aunque te podría servir simplemente dejar como "pre-fijo" al nombre del archivo un ID (si es que gestionas tus datos sobre una BBDD y previamente lo obtienes) o un microtime() .. o aplicar la función "uniqueid()" .. o similar. El caso es que a su vez .. cuando tengas generado tu nombre de archivo definitivo (con tu "pre-fijo") verifiques que no exista el archivo: file_exists()
Un saludo,