A hard bounce is an indication that you should never send a message to that address. The bounce message should contain an indication as to why you were bounced. If the address does not exist, then no amount of waiting is likely to resolve the issue.
If you get a soft bounce, such as you should get for over quota, use an exponential backoff. This should be part of the default ruleset for your mail server. Fail the message after at least two days. If you back off to daily retries, it is common to wait at least a week before failing the message. You may want to periodically (first failure, and after a day or two) notify the sender of the delay.
If you were hard bounced because of your configuration, then wait until you have resolved the issue. My mail server blocks for many of these conditions which may result in a hard bounce:
- Improper DNS entries. Your address must resolve from IP address to DNS name and back to the same IP address. This is part of the RFC.
- Sending email directly from a dynamic address. Use your ISP's relay, or another relay which requires authentication. (You will likely be violating DNS conditions above rule as well.)
- Being blacklisted. Almost all the blacklists will allow you to get off them reasonably quickly. You can also get blacklisted at the receiving site, which can be more difficult to resolve.
- Sending from an address not allowed by your SPF (Sender Policy Framework) DNS entries.
- Supplying incorrect data when you send your HELO or EHLO message. This should be the fully qualified DNS name corresponding the the IP address. localhost, GEORGE, MY_HOST, and such are not valid, but may be accepted. Also claiming to be the host you are sending to or another host in their domain is not valid.
- Sending incorrectly formatted messages. Missing headers, invalid dates, etc.
- Sending a message which is identified as SPAM by a spam filter.
- Sending from an address which can not be verified. Your IP address should be allowed to send from that domain.
- Sending from an address belonging to a domain that is handled by the receiving system. This should require you to authenticate as the sending user first.
- Using a message id indicating that the message was sent from the receiving domain.
- Running an open relay.