Thanks for the reply.
Interestingly, the IP address I was using had all indications of being clean (not on any blacklists).
I decided to ditch Digital Ocean, and instead move over to Linode in the hope that I’d have some more luck. I checked the IP for my new box and confirmed that it was clean. I also ensured my DNS was perfect with regards to SPF, DKIM etc.
Strangely, this move resolved the issue with Google, and for the moment all of my emails are appearing in the inbox and bypassing spam.
The issue did however worsen with Outlook. Instead of the emails never arriving, I actually got an undeliverable report containing the following text:
Reporting-MTA: dns; mlxxx.xx.xxx.com
X-Postfix-Sender: rfc822; firstname.lastname@example.org
Arrival-Date: Sun, 1 Nov 2015 11:33:19 +0000 (GMT)
Final-Recipient: rfc822; email@example.com
Remote-MTA: dns; mx4.hotmail.com
Diagnostic-Code: smtp; 550 SC-001 (BAY004-MC5F31) Unfortunately, messages from
220.127.116.11 weren’t sent. Please contact your Internet service provider
since part of their network is on our block list. You can also refer your
provider to http://mail.live.com/mail/troubleshooting.aspx#errors.
I did some digging and found [this page] on the Microsoft Support website that enabled me to request that my IP ranges are unblocked. I got a reply within an hour saying the following:
We have completed reviewing the IP(s) you submitted. The following table contains the results of our investigation.
Our investigation has determined that the above IP(s) qualify for conditional mitigation. These IP(s) have been unblocked, but may be subject to low daily email limits until they have established a good reputation.
Please note that mitigating this issue does not guarantee that your email will be delivered to a user’s inbox.
Ongoing complaints from users will result in removal of the mitigation.
Mitigation may take 24 - 48 hours to replicate completely throughout our system.
If you feel your issue is not yet resolved, please reply to this email and one of our support team members will contact you for further investigation.
Regardless of the deliverability status, Outlook.com recommends that all senders join two free programs that provide visibility into the Outlook.com traffic on your sending IP(s), the sending IP reputation with Outlook.com and the Outlook.com user complaint rates.
Junk Email Reporting program (JMRP) When an Outlook.com user marks an email as "junk", senders enrolled in this program get a copy of the mail forwarded to the email address of their choice. It allows senders to see which mails are being marked as junk and to identify mail traffic you did not intend to send. To join, please visit http://support.msn.com/eform.aspx?productKey=edfsjmrpp&page=support_home_options_form_byemail&ct=eformts.
Smart Network Data Services program (SNDS). This program allows you to monitor the ‘health’ and reputation of your registered IPs by providing data about traffic such as mail volume and complaint rates seen originating from your IPs. To register, please visit http://postmaster.live.com/snds/.
There is no silver bullet to maintaining or improving good IP reputation, but these programs help you proactively manage your email eco-system to help better ensure deliverability to Outlook.com users.
Outlook.com Deliverability Support
After this, my emails were no longer refused, but do still go straight to spam. I have now resorted to rallying as many family and friends as possible, and have been sending them emails and getting them to both mark them as non-spam, and also to reply to me so I can try and build up some trust.
I’ve also tested the deliverability with Yahoo, and AOL, and have also found that emails go straight to Spam. Clearly this isn’t a fault or flaw with MIAB, it’s just the problem you get with being a small fish in a big pond.
I have however decided that I am not going to be bullied into re-centralising, I am going to work to improve the reputation of my IP.
If anyone is up for it, I think the MIAB community should all share our email addresses for the mainstream providers with eachother, so that we can all mark eachothers mail as non-spam. This should help with training those pesky spam filters.