Eso si sigues teniendo una tabla para cada letra (cosa no recomendable).
Pero funcionará sólo con la primera página. Pues al ir a la página 2 esa variable $_POST['letra'] no existirá porque ya no vienes de un formulario sino de un enlace.
A eso es a lo que me refiero con propagación de variables. Tienes que ver la manera de que esa variable (con la letra seleccionada) llegue también a las otras páginas.
Vuelvo a recomendarte que le des una mirada al código de Paginator que ya hace todo eso además de ser muy sencillo (es casi igual a lo que haces tú pero acomomodado de tal manera que sea más sencillo de utilizar).
Pero, insisto, mejor es que tengas una sola tabla con un campo que defina esa letra y no ¿27?... ¿29? tablas (Wow).
Saludos