Fernando, creo que si sustituyes la linea que has puesto en rojo:
"lcd.begin(16, 2);" por la que te dije de limpiar el display "lcd.clear();" te puede funcionar tambien.
Esto es suposicion pero, es posible que tuvieras que limpiar el buffer del puerto serie con el "serial.flush()" lo de los caracteres raros, si no son retornos de linea o CR, solo se me ocurre que llene el display y como no tiene funcion de autoscroll machaque datos. Pero es solo suposicion.
Esto es intentando imaginar porque no se como pilula el encoder, si te manda numeros en negativo o algo, o es que pierde sincronizacion, o llena buffer, o es solo el display.
Probablemente la orde que tu le das de "lcd.begin(16, 2);" lo que haga es inicializar el display aparte de definirlo, por eso veas bien los caracteres, pero ya te digo, es solo un intento de imaginar, no te puedo decir a ciencia cierta.
Un saludo y suerte con ello
PD: Se me olvidaba, en este enlace que te dejo tienes los datos extendidos del display compatible hitachi aparte de la tabla de caracteres a ver si consigues identificar que codigos son:
http://www.sparkfun.com/datasheets/LCD/GDM1602K-Extended.pdf