Found the issue.
In the example I posted, on the Ethernet.Begin() I only provided the MAC and IP.
Which makes the default subnet default to 255.255.255.0 according to the documentation on, Ethernet - Arduino Reference
So I added dns, (which apparently was already defined in Dhcp.h and caused a compile error), then gateway and then finally the correct subnet, 'Ethernet.begin(mac, dns,ip,gateway,subnet);'
From here on, everything worked perfectly as expected. Except for having to add a delay(1000); after the Ethernet.begin() before calling any other Ethernet related functions. Without the delay Ethernet wouldn't work at all, except for right after the programming. But as soon as you reset/reboot the Arduino, it wouldn't work ever again until programmed again.
However!!
A lot of examples and documentation on the site don't seem to mention 'dns' in the Ethernet.Begin()
Worse yet, they are often documented/used as followed
Ethernet.begin(mac, ip, gateway, subnet);
Which is completely non functional! As this will make the device lookup the mac address for the ip of the given subnet!
The subnet in this example will still be the default, the gateway will be the subnet, and the dns will be the gateway.
This obviously creates problems and doesn't work.
However, weirdly, it does work if you swap places of subnet and gateway in this example.
Ethernet.begin(mac, ip, subnet, gateway);
Then it suddenly gets the subnet right and I was able to communicate with the Arduino.
Very odd if you ask me because according to the documentation, the subnet should still be the default as that's the 5th parameter which wasn't provided.
Either way, everything is working fine now using the code below
#include <SPI.h>
#include <Ethernet.h>
#include <EthernetUdp.h>
byte mac[] = { 0xDE, 0xAD, 0xBE, 0xEF, 0xFE, 0xED };
IPAddress ip(10,9,10, 10);
IPAddress gateway(10,9,1, 1);
IPAddress myDNS(10,9,1,111);
IPAddress subnet(255, 255, 0, 0);
void setup() {
Ethernet.begin(mac, ip,myDNS, gateway, subnet);
delay(1000);
}