RichFaces com Paginação no Banco

Bom dia galera.

Estou tendo o seguinte problema na minha aplicação:

Tenho um rich:datamodel na minha página, e para efeitos de performance, faço a busca de 30 elementos de cada vez.
O problema ocorre quando eu tento ordenar os dados da lista.
Exemplo:
Na busca, retornou 40 elementos, portanto serão apresentadas 2 páginas.
A primeira página fica correta, com a ordenação perfeita.
Já na segunda página acontece o seguinte:
Essa é a maneira como deveria aparecer:
A
B
C
D
E
F
G

Essa é a maneira como está aparecendo:
E
F
G
A
B
C
D

Isso acontece com qualquer ordenação que faço: sempre os 3 primeiros elementos da última página, são apresentados nas últimas posições da lista.

Alguém já passou por isso?