Q:

How to create DNS records for my VPS

first of all I should mention that I'm fairly new to the world of DNS. I've purchased a VPS plan and I'm trying to run a web server and also a custom mail server (postfix and dovecot combination), which turns out to be a real pain. I'm aware of the fact that I can make my life easier by using Google App services but nonetheless I want to be able to do it myself. 
I'm stuck with so called DNS records and as far as my understanding goes I should first of all create an A record for my mail.mydomain.com and afterwards a MX record, am I right? I checked every option my hosting provider provides, but unfortunately I couldn't find anything. 
If I run: 
nslookup -q=mx mydomain.com
it gives me: 
Non-authoritative answer: 
mydomain.com    mail exchanger = 10 mail.mydomain.com
and for "Authoritative answers" I get nothing.
So first question: "'Authoritative answers' are answers from mydomain.com itself and to be able to give such answers I should run my own DNS Name Server and have so called 'zones file' in which I have these records setup, am I right?". 
And following question would be: "to be able to do it I should have 'bind' software package installed, right?".
Another question: "if haven't done any of it how come I get 'Non-authoritative answer' for my MX query? Does it mean I already have one MX record from my service provider?". 
And the last question would be, since it is for a custom mail server and if you are familiar with it: "could you tell me why do I have to have a reversed domain record (I think it is called PTR) in order to avoid my mail get landed in spam folder?"

A:

You got Non-authoritative answer because you did not query records from name servers of the domain, and the results may contain IPs.
This result is similar as yours.
$ nslookup -q=mx google.com
Server:         8.8.8.8
Address:        8.8.8.8#53

Non-authoritative answer:
google.com      mail exchanger = 30 alt2.aspmx.l.google.com.
google.com      mail exchanger = 20 alt1.aspmx.l.google.com.
google.com      mail exchanger = 40 alt3.aspmx.l.google.com.
google.com      mail exchanger = 50 alt4.aspmx.l.google.com.
google.com      mail exchanger = 10 aspmx.l.google.com.

Authoritative answers can be found from:
alt3.aspmx.l.google.com internet address = 173.194.204.26
alt4.aspmx.l.google.com internet address = 74.125.141.26
alt2.aspmx.l.google.com internet address = 173.194.219.27
aspmx.l.google.com      internet address = 74.125.25.26
alt1.aspmx.l.google.com internet address = 74.125.193.27

So we can find name servers of the targeted domain.
$ nslookup -q=ns google.com
Server:         8.8.8.8
Address:        8.8.8.8#53

Non-authoritative answer:
google.com      nameserver = ns3.google.com.
google.com      nameserver = ns1.google.com.
google.com      nameserver = ns2.google.com.
google.com      nameserver = ns4.google.com.

Authoritative answers can be found from:
ns3.google.com  internet address = 216.239.36.10
ns2.google.com  internet address = 216.239.34.10
ns1.google.com  internet address = 216.239.32.10
ns4.google.com  internet address = 216.239.38.10

Then we can get authoritative answer.
$ nslookup -q=mx google.com ns1.google.com
Server:         ns1.google.com
Address:        216.239.32.10#53

google.com      mail exchanger = 40 alt3.aspmx.l.google.com.
google.com      mail exchanger = 10 aspmx.l.google.com.
google.com      mail exchanger = 30 alt2.aspmx.l.google.com.
google.com      mail exchanger = 50 alt4.aspmx.l.google.com.
google.com      mail exchanger = 20 alt1.aspmx.l.google.com.

As the sample you posted, you can confirm if mail.mydomain.com has pointed to a IP ( so called A record ), and mail related services maight be OK if there are correct MX & A records.
You should find out name servers of your domain before you maintain the DNS records.
I guess your service provider ( or someone else ) have set up MX record of your domain, you may get more answers from your service provider.

