Bom, vou fazer uma pergunta porque a partir da resposta do Guilherme Nascimento eu achei a resposta.
O problema não e um problema de COLLATE mas um problema entre Mysql et PHP. Sabemos que PHP não usa utf8. Foi previsto para PHP6 mas vai 'teoricamente" acontecer somente em PHP7.
Vamos então ver como fazer um site em utf8 para entender a dificuldade.
No inicio, vou criar minha BDD e depois as tabelas. Tudo em utf8. Quando vou testar, usando o teste de Guilherme Nascimento, ta tudo certo. Legal!
Depois vou criar meu codigo PHP e criar a pagina HTML onde vou colocar:
<meta content="text/html; charset=UTF-8" http-equiv="content-type" />
Depois vou criara um documento php, onde vou colocar por exemplo:
define ("TITULO","Direção");
vou salvar em UTF8 e enviar usando um software FTP, que não vai mudar o código.
Vou criar uma pagina com um formulário e um campo INPUT usando o titulo definido no meu define.
Legal! Vou ver "Direção" como titulo, vou digitar por exemplo "direção nacional" no campo. No submit, o conteúdo vai ser enviado na segunda pagina PHP e eu vou salvar usando um SELECT.
Na leitura, vou simplesmente fazer um SELECT * FROM TAB. Vou fazer um echo colocando titulo e depois o contendo da minha tabela e vou ter:
Direção: direção nacional
Neste momento, eu vou ter certeza que tudo esta certo. Mas não é. De verdade, dentro da tabela, eu não tenho "direção nacional". Eu tenho "dire��o nacional". Mas como na leitura, tem conversão automática dos dados, isso ma da a ilusão que os dados são corretas. O problema e que, quando eu vou precisar fazer um ORDER BY, MySQL vai fazer usando "dire��o nacional" e o resultado vai ser errado.
No seu exemplo Guilherme Nascimento usa um fiddle então, um sistema fechada. O que explica que funciona perfeitamente.
Soluçao
A solução e simples. Imediatamente depois do mysqli_connect, precisa colocar mysqli_set_charset.
$handle = mysqli_connect($sql_host,$sql_user,$sql_password,$sql_database);
mysqli_set_charset($handle,'utf8');
A partir disso, quando vc vai digitar "direção", na tabela vai ter "direção" e o ORDER BY vai ser coreto.
Mas, para os dados antigos???
Infelizmente, exportar para re-importar vai mudar nada. Porque eu vou exportar "dire��o nacional" e reimportar "dire��o nacional". De verdade, precisa ler os dados SEM fazer o mysqli_set_charset, depois fazer o mysqli_set_charset e fazer um INSERT.
Então:
1 - Conectar usando mysqli_connect (sem fazer o mysqli_set_charset)
2 - Ler os dados da tabela e salvar para preparar o query para INSERT elas
3 - Fazer um TRUNCATE na tabela
4 - Fazer o mysqli_set_charset($handle,'utf8');
5 - Fazer o INSERT dos dados
Assim, vou ler da forma "antiga" e depois, vou "insert" da nova forma.
Agora, tudo esta certo!!