Cita: Por otro lado, los demás usuarios descritos el Administrator designó a cada uno así:
ej. maria@any host. Sin embargo, no puede conectarse desde su pc remota. Aquí es donde estoy confundido.
Hay que ver qué es lo que quedó realmente en MySQL, porque "anyhost" es un host denominado así. Para que sea desde cualquier host, debe ser "%".
Por otro lado, crear el usuario solamente es insuficiente, puede darse que esté correctamente dado el permiso de conexión remota, pero si no les das por lo menos permisos de SELECT, el usuario no puede ni siquiera entrar en sesión.
Fijate cuáles son los permisos reales de cada usuario.
PD: Hay un capítulo entero del manual de referencia de MySQL dedicado a la administración de usuarios. ¿Lo has mirado un poco?
MySQL :: MySQL 5.0 Reference Manual :: 5.7 Gestión de la cuenta de usuario MySQL