If anyone is interested, I have found out why this was not printing (thanks to Linuxprinting.org).
Despite what I thought before, the fix is doesn't have anything to do with Linux.
On the Windows Printer properties there is a tickbox that enables Bi-Directional Printing (allows the printer to tell Windows when it's out of ink etc).
This should be unchecked so that Bi-Directional Printing is disabled.
Works great now