The PTR record must resolve correctly in both directions. Say I did a reverse lookup on a connecting IP of 1.2.3.4 and it gave me 'PTR mail.spongebob.squarepants'. I should then be able to do a forward A lookup for mail.spongebob.squarepants and get 1.2.3.4 as the answer.

I suspect your PTR record text does not resolve back to the same IP that is connecting to hotmail - but it's a guess.

I don't really get what it outputs when I nslookup the ; first it says

I don't really get what it outputs when I nslookup the ip it says;

And for mail.mydom.com;

I translated the non-English parts so they may not be perfect.
I also had to try restarting the system cuz some company software used only within the company that uses the mysql server on the server was very very slow and nothing changed after the restart. I'm getting close to an end here

Don't throw in the towel just yet :-)

I don't have any serious issues with the DNS PTR records - google refuses to list AUTH NS for the reverse zone, but using my ISP I get ns1/ns2.tr.net.tr as auth for PTR. It's not blacklisted anywhere obvious that would give you issues. Hotmail may have some local policy kicking you and you'd need to examine the error message in the logs/bounce message to get a handle on that.

My advice would be if you don't have a specific need to run your own AUTH dns servers then don't! I've had to run my own because my domain registrar did not support DKIM and I needed it, but I have other hosts where the registrars own name servers are perfect for 10 or so domains (it gets a PITA using a web interface much beyond that). This should resolve the issue for your users - which is the end game we want here. My own suspicion is they are unable to reach your name servers from time to time. When I queried google for your MX it had cached the result, but hung at:
This could be an issue for external clients because they may not have a cached result for one of your domains, and with the result for the auth server timing out I would imagine they would get the phenomena you are experiencing.

If you want to troubleshoot this more can you reply to the email I sent you to 'postmaster' with the name of one of the troublesome domains and I'll see if I can recreate this externally :-)

Ok I won't : )
Here is the result when I tried to reply to your email using outlook;

And this is the company where we have our server;

You know what, when I do;
I get;
But if I do;
I get;
Could this be causing some confusion in the dns servers in between somewhere? But then again, that slow mysql connection should be due to something else I guess, since it's done directly through the ip.

Nothing in my logs, but this much I know:- I don't get *ANY* IP address for ns1.ixxxxxo.com or ns2.ixxxxxo.com from outside. Just the SOA marker. Looks like you failed to set up entries for ns1/ns2 in the zone. I appreciate you want to protect your privacy but without seeing the named.conf and affected zone files I can only give you general pointers

1 members found this post helpful.

Here's the named.conf;
So there's nothing about the nameservers here, n1-ns2.mydom.com, should there be?
The master zone files are as follows;
And this is the domain for which name servers are defined - the file called mydom.com.db ;

Anything missing or extra?

I had searched aaa looott when I was first looking for such examples, hope these help others.
I was told by some god - I mean guy that I'm missing A records for the ns1 and ns2 records in the mydom.com.db file like these;