A dead e-mail identification locator discovers dead e-mail addresses without forwarding messages to valid recipients. Existing headers in the mail protocol are extended to include a test header. A mail server that supports the protocol extension of the present invention may send a reply if the address does not exist and may discard the message if the address does exist. The test header allows a sender to test an e-mail address for validity without the message being forwarded to the user, as will be described below. The sender may be a dead e-mail locator program, which tests a plurality of e-mail addresses. The sender and recipient mail servers may include attributes in the test header to enhance the analysis of delivery failures. Using these attributes, the dead e-mail address locator can pinpoint the location of e-mail message delivery failure and profile the performance of routing of messages and other details hidden from users.