Yo creo que no se "imprime" basura. Yo creo que lo que tu ves como basura es el valor binario de los enteros, por lo que yo te aconsejo que sigas usando fwrite:

fwrite(&cnt, sizeof(clientes), 1, archivo);

Estás seguro de que has inicializado la estructura andes de guardarla? También ten en cuenta que la cadena tiene longitud 50, por lo que si por ejemplo la cadena es "Carlos", entonces el resto de bytes de la cadena contendrá basura. Te pongo un ejemplo con una cadena de 10 elementos. Supongamos la siguiente cadena:

char cadena[10] = "Cadena";

Dada la información, el arreglo cadena contiene 'C', 'a', 'd', 'e', 'n', 'a', '\0', pero, ¿qué pasa con el resto de bytes de la cadena? Pues simplemente están llenos de basura, pero eso no pasa nada, para eso está el indicador de final de cadena ('\0'). La cadena se vería así:

'C', 'a', 'd', 'e', 'n', 'a', '\0', BASURA, BASURA, BASURA

donde basura vale cualquier valor "aleatorio"

Creo que no me has entendido, una vez pasado el caracter nulo, da igual lo que haya guardado en la cadena, pues siempre leerás desde el principio de la cadena hasta el carácter nulo, así que si se guarda 'basura', no pasa nada. Si de verdad te molesta esa basura, simplemente inicializa el arreglo con caracteres nulos, y ya después almacenas la cadena en si.