The problem is probably not what your server does, but what its DNS identity looks like when viewed from the internet.
If the email is sent from a system that claims to be servername.mydomain.com but whose IP address does not match the address reported by the public internet DNS for servername.mydomain.com, then of course the email is going to be classified as spam by the recipient server, as it is clearly a crude source address forgery attempt. The PTR "reverse DNS" records are an essential part of this verification. For example, if your public IP address is A.B.C.D, then the PTR record should be D.C.B.A.in-addr.arpa. IN PTR servername.mydomain.com.
This is one of the oldest anti-spam tests.
If your Ubuntu web server does not have a static IP address and a valid DNS registration (both forward and reverse DNS records in agreement with each other), you should not be sending email out directly, but instead sending all outgoing email to a mail server that satisfies these conditions. Maybe your hosting provider has a mail server you would be allowed to use?
This is known as "smarthost configuration". See this question for a minimal configuration example.
However, a modern hosting provider might require you to use SSL/TLS encryption and authentication when submitting outgoing mail. In that case, see here.
Unfortunately, there are too many clueless home users that allow their systems to become infected. As a result, outgoing email originating directly from IPs with a non-matching PTR record or from known home-user IP blocks tends to get auto-classified as spam, as much of modern email spam is generated by infected hosts that become members of a spammer-controlled botnet.
Since the PTR records, unlike any other DNS record types, are zoned according to IP address blocks, the PTR record of your public IP address is probably under control of your network provider. Have you tried contacting them? If you have a static public IP, assigning a custom PTR record for it would technically be possible, but they might have made a policy decision not to offer such services for home customers, in which case you might be stuck with a requirement to send outgoing emails through the network provider's mail server.
An alternative approach might be setting up your sendmail to introduce itself to the world using the actual fully-qualified domain name that is claimed by the PTR record, and then adding SPF / DKIM / DMARC records to your domain to list that FQDN as the authorized email sender for your domain. Since SPF/DKIM/DMARC records are all TXT-type records, you should have no problem adding them to your domain.
A properly implemented SPF/DKIM/DMARC set-up might generate enough positive anti-spam points in the recipients' spam filters to offset or even completely override the negative hit caused by the "originating mail server's domain from the PTR record does not match the claimed From: address" check.
You should also use one or several of the free mail server testing tools available on the internet to see how your mail server "looks like" in terms of anti-spam checks; for example, this one here.
With the results of those tests at hand, it should be much easier to find and fix the main cause of your outgoing mail getting classified as spam than by just guessing at typical reasons.
