Do I need to create a DNS record on the nameserver that points
server1.example.com to the VPS's IP address ?
Yes, you do. As @HBruijn commented, you need to have a PTR record (reverse DNS)
so that when a remote host does a reverse look up of your IP number to get the name of your server, it will receive the PTR record server1.example.com.
Likewise, when people have your server's name and try to look up your IP number, you need an A record so that they get the correct IP number for your server.
Assuming that your server is named server1.example.com
and your IP number is 10.216.177.146
, anyone with access to the public DNS needs to be able to:
$ host 10.216.177.146
146.177.216.10.in-addr.arpa domain name pointer server1.example.com.
$ host server1.example.com
server1.example.com has address 10.216.177.146
The key element here is that the second lookup returns the same IP (10.216.177.146) that was used in the first lookup.
The logic behind it goes something like this:
1) when your server opens a TCP connection to deliver outbound mail, the only thing the receiving server knows is your IP number, 10.216.177.146, at least at first.
2) since all it has is an IP number, it does a reverse lookup, and obtains the PTR record for 10.216.177.146. That should return server1.example.com.
3) since PTR records can easily be forged (and set to a value to try to impersonate some other entity), the remote server then does a forward lookup on the PTR it received. That lookup of server1.example.com
should return 10.216.177.146, and that sounds like the piece (the A record) that you're still missing.
It is this PTR record -> A record -> PTR record chain that establishes what is referred to as matching forward and reverse DNS and gives the remote server a modicum of confidence that your server is authorized to use the name server1.example.com.
Other tests are done in addition to this (such as the SPF and DKIM tests refered to in the other answers and comments), but some servers won't even accept your mail if you don't have matching forward and reverse DNS.