you made a statement that you are able to telnet with that user on port 110 succesfully. So that means the mail box does exist on the server then. Try using another mail client then, there might be a type-o or a misconfiguration with the client version in eudora?
But your question answered a previous question I had and Id like to thank you.
Hope my suggestions helps in some way or confirms your suspicons