The largest issue is often where you are hosting it – the address/range might not be well trusted due to either how it is categorised (if it is address known to

The largest issue is often where you are hosting it – the address/range might not be well trusted due to either how it is categorised (if it is address known to be assigned to residential accounts then all mail may be dismissed as junk from a compromised host without any inspection) or who has used it before you (if using an inexpensive VPS (or dedicated server) provider the addresses you have may have been used by a spammer in the past). I've had very few problems with my home server sending mail, but I'm with an ISP more known for commercial users (so they take keeping their ranges clean seriously, and they aren't listed in IP databases as residential), I've had these addresses for over a decade (back when you could get a /29 fairly easily if not using a cheap ISP) so no one has sent junk from them (actually a friend was infected by something that sent web junk out, but that goes over the primary address not the range the mail service is on), and so forth. The easiest way to solve this if you aren't as lucky as I am, is unfortunately not a free solution: send via a 3rd party relay such as companies like mxroute offer – you still control your entire mail server, your store all the mail, etc, but someone else deals with final delivery of outgoing mail (a good provider will multiple outgoing feeds themselves and deal with resending in response to some types of rejection, as well as making sure all their outgoing routes are reputation clean). For small volumes this is actually quite cheap, potentially far less expensive than your admin time dealing with delivery failures yourself. Other common issues are not having SPF records set properly, or not implementing DKIM signing. Both of these are now essential and have been for some time, whether you send directly or via a 3rd party MTA, so if you didn't verify those that could be your issue. Also, some mail receivers don't trust brand-new domains (the newest domain my main mail server regularly sends for was registered in 2010) so if you tested the mail server with a throwaway domain that could be a significant part of the problem. If you want to use a throwaway domain for testing, at very least wait until after the 5-day “domain tasting” grace period. Also pick a throwaway domain name that is relatively long and otherwise unlikely to have been used before (and unlikely to have ever been used as a from address in junk messages).