Refuse mail is only available for incoming (recieve) emails. This means that the Exchange Server is currently recieving the email but has yet to accept it. The rule action allows to refuse to accept the email and return an error message to the sender.
Do not deliver mail does not depend on the current status of the email. The rule action will have the Exchange Server quietly discard the email without delivering it.