The proportion of spam has significantly increased in recent years. This paper proposes an extended differentiated mail transfer protocol (extended DMTP, namely EDMTP) to deal with the problem that the graylist is unclearly categorized in DMTP. Considering the difficulty in promoting the common problem of protocol, we design EDMTP-based schemes on SMTA (sending Mail Transfer Agent) and RMTA (receiving Mail Transfer Agent). Our new schemes accord with open close principle and do not need changing the original mail infrastructure. In addition, we design experiments to compare EDMTP with DMTP. Simulation results demonstrate that EDMTP can reduce the number of envelopes and the proportion of spam envelopes and therefore significantly improve the performance of graylist. Moreover, compared to the current SMTP-based e-mail system, our proposed EDMTP-based e-mail system can effectively decrease the traffic usage of spam.