Postgresql – Unable to remotely connect to Postgresql 9.5 instance

I am struggling to connect to a remote Postgresql 9.5 instance running on Ubuntu 16.10.
The usual:

psql: could not connect to server: Connection timed out
Is the server
running on host "xx.xx.xx.xx" and accepting TCP/IP connections on
port 5432?

My postgresql.conf includes

listen_addresses='*'

confirmed by output from

netstat -nlp | grep 5432
tcp        0      0 0.0.0.0:5432            0.0.0.0:*               LISTEN      22981/postgres      
tcp6       0      0 :::5432                 :::*                    LISTEN      22981/postgres      
unix  2      [ ACC ]     STREAM     LISTENING     3320886  22981/postgres       /var/run/postgresql/.s.PGSQL.5432

Apart from my specific IP address & range, I have also tried the following entries in pg_hba.conf:

host    all             all             0.0.0.0/0               md5                                                                                                                                                                                       
host    all             all             ::/0                    md5
host    all             all             all                     md5
host    all             all             *                       md5 

I have the following ufw rules:

To                         Action      From
--                         ------      ----
22/tcp (OpenSSH)           ALLOW IN    Anywhere                  
80,443/tcp (Nginx Full)    ALLOW IN    Anywhere                  
5432                       ALLOW IN    Anywhere                  
22/tcp (OpenSSH (v6))      ALLOW IN    Anywhere (v6)             
80,443/tcp (Nginx Full (v6)) ALLOW IN    Anywhere (v6)             
5432 (v6)                  ALLOW IN    Anywhere (v6) 

However, the problem persists even when disabling the firewall.

Scanning with nmap:

nmap xx.xx.xx.xx -p5432

Starting Nmap 7.01 ( https://nmap.org ) at 2017-02-13 09:17 SAST
Nmap scan report for xx.xx.xx.xx
Host is up (0.0074s latency).
PORT     STATE    SERVICE
5432/tcp filtered postgresql

Almost all similar questions on SE seem to be solved with

listen_addresses='*'

which is not an issue here.

Really confused by this, help would be greatly appreciated.

The machine is not down as I am able to ssh into the machine. Additionally nginx server is also accessible. Telnet to port 5432 times out.

There is no local router in front of the ubuntu server, it is a dedicated server with public network interface that is bound to the xx.xx.xx.xx address. This is a migration from a previous generation box at the same hosting company who does not offer the option of an additional firewall device. This is a clean Ubuntu 16.10 server install.