Primoridal pseudonymous remailers once recorded enough information to trace the identity of the real user, making it is possible for someone to obtain the identity the real user through legal or illegal means.
This form of pseudonymous remailer is no longer common.
David Chaum wrote an article in 1981 that described many of the features present in modern pseudonymous remailers. (Untraceable Electronic Main, Return Addresses, and Digital Pseudonyms; Communications of the ACM; Vol. 24; Number 2)
The most popular pseudonymous remailer was the Penet remailer, which lasted from 1993 to 1996.