Quanto devemos mostrar se o usuário clicar no final de uma longa lista de páginas?
Deixe-me dar um exemplo do que quero dizer com uma longa lista de páginas: 
Portanto, quando você clica em 19, é necessário determinar quantas novas páginas serão exibidas e quantas páginas antigas não serão exibidas.
Por exemplo: 
Quantas páginas novas você deve e quantas páginas antigas você não deve exibir?
Aqui está a resposta oficial da Yahoo Developer Network - Biblioteca de padrões de design em Search Pagination :
Quando em qualquer página após 6 (7 em diante), os links da página devem começar na página atual menos 5. Por exemplo, quando na página 7, a primeira página será 2 (7 - 5 = 2) e a última página será 11 (ainda mostra 10 páginas).
Suponho que depende de como você acha que seus usuários vão querer interagir com seu conteúdo.
Por exemplo, ao folhear arquivos do blog, acho que um modelo simples mais antigo/mais recente funciona, especialmente quando várias entradas do blog são mostradas em uma página (e existe um arquivo mais abrangente, como postagens por mês/categoria/qualquer outra coisa).
Em coisas como fóruns, costumo concordar com o modelo "1 ... 7 8 9 ... 30". Não acho que o número de páginas no "centro" dos números das páginas seja importante, desde que não seja excessivo demais. Pode ser menor se você não esperar que que muitas páginas existam ou mais se você espera uma quantidade enorme de páginas (ou seja, google, conforme o exemplo da sua pergunta).
Existem vários outros modelos que podem funcionar, dependendo do que você está paginando (por exemplo, "prev, next, vá para a página:"), mas, como muitas coisas, depende. Não existe uma resposta universalmente correta.
Mas, não é isso grande coisa, afinal. Se você estragar o seu modelo de paginação, tenho certeza de que não haverá uma quantidade significativa de dano, desde que seja um pouco utilizável.
Como podemos responder às nossas próprias perguntas: pelo que notei, a maioria dos sites exibe duas páginas novas e duas páginas antigas.
Por exemplo:
Então, quando eu atingi 5 (que é o fim da lista):
Acho a paginação do fórum vBulletin a mais útil. Se você estiver em uma página nº 1000 de 5000, ela mostrará:
<< Primeiro <Anterior ... 500 900 950 990 998 999 10 1001 1002 1010 1050 1100 1500 2000 ... Próximo> Último >>
Ter 10, 50, 100, 500 etapas é bastante conveniente e eu geralmente as uso muito.
A capacidade de pular para um "número da página" geralmente é útil apenas nos casos em que o material está por ex. a quinta página em um determinado momento provavelmente permanecerá lá por algum tempo. Caso contrário, conseguir mostrar a página "próxima" e "anterior" cheia de coisas é útil, mas qualquer navegação além dela deve ser baseada em qualquer critério usado para classificar os itens da lista. Se houver vinte páginas de autores classificadas por nome, tenha links para letras ou intervalos; se o usuário clicar em uma letra com mais de um valor de entradas, mostre nomes desde o início dessa letra, mas adicione links com intervalos de nomes.
Da mesma forma, se os itens são classificados cronologicamente, têm links por anos e meses e, se necessário, subdividem por horas ou minutos.
Se 5.000 páginas no valor de itens são classificadas cronologicamente, a possibilidade de pular para páginas específicas pode permitir que alguém que queira um item para uma data específica se hospede nele sem precisar clicar em "próximo" 2000 vezes, mas se o que o usuário deseja for para encontrar uma data específica, seria melhor permitir que o usuário especifique a data do que exigir que ele adivinhe uma página, veja o que está lá, refine sua adivinhação etc.