Na página inicial do phpMyAdmin, vá para Configurações> Painel principal> Modo de navegação (ou Configurações> Quadro principal para versões antigas) e desmarque a opção Lembrar classificação da tabela e clique em Salvar .

Então, ao navegar em uma tabela, você pode classificar as colunas como de costume, mas clicando em Procurar novamente irá remover a classificação.

Testado nas versões 3.5.2.2 e 4.0.10.14.