Bem, o facto de o ip ser da veloxzone nao quer dizer nada, nao sei muito acerca dos provedores do brasil mas provavelmente a embratel ta conectada a veloxzone e portanto o seu ip pode continuar a ser designado como pertencendo a veloxzone.
Voce esta a usar uma conexao via router, ou liga directamente pelo modem?
Se isso so aconteceu apos mudar de provedor, e possivel que a embratel bloqueie as portas do eMule para os seus clientes nao fazerem "downloads ilegais" ou obstruirem os servidores.
Para isso mude as portas de conexao utilizadas pelo eMule (as portas TCP e UDP). Para proceder a tal alteracao, abra o menu "Preferencias" e em "Conexao" mude os numeros das portas TCP e UDP. Apos isso reinicie o seu modem e o seu pc, verifique se o teste ja passa ou nao