AES (Rijndael) utiliza el mejor código de encriptación hasta ahora desarrollado, y que según se explica en diversos artículos, es el que está en uso por el gobierno de EE.UU. actualmente.
En ese sentido, se lo considera mucho más seguro que el MD5. Y no, el objetivo de un código de encriptación no es que no se lo pueda desencriptar, sino que no se lo pueda
quebrar, es decir, que nadie que no tenga la clave de encriptación pueda, a su vez, desencriptarlo.
El nivel de seguridad del aes está plenamente confirmado por documentación (ver
documento).
Por todo esto, el problema no tiene que ver con la capacidad de encriptar o desencriptar que el método AES_ENCRYPT tenga. Tu problema puede tener otro origen.
Yo veo dos posibilidades:
1. Existe algún conflicto con las COLLATION usadas en tu base y en el server de internet.
2. Existe algún tipo de problema en cuanto a la longitud de la clave almacenada. Esto lo he visto antes. Para el caso, por ejemplo, aunque tu pongas un password para un user de MySQL de 3 caracteres, la clave encriptada tendrá 41. En el caso de AES, la clave encriptada tendrá como mínimo 16, no importa qué pongas, pero puede tener muchos más (256, según entiendo). ¿Estás almacenando la cantidad correcta de bytes?