Exchange 2007 with 2003 OWA Activesync Error 503

I was receiving this error on our front-end 2003 OWA server, which is connecting to a 2007 mailbox server and has ISA:

HTTP status code: [503]. Verify that the Exchange mailbox Server is working correctly.

I was also receiving this error:

The mailbox server does not allow "Negotiate" authentication to its [exchange] virtual directory. Exchange ActiveSync can only access the server using this authentication scheme.

Users couldnt use their iPhones to connect to Exchange. Indeed Windows authentication and basic authentication were enabled.

I tried everything and ended up rebuilding the Exchange virtual directory by doing:

remove-owavirtualdirectory -identity "server\exchange (default website)"

and recreating it:

New-OWAVirtualDirectory -OwaVersion:Exchange2003or2000 -VirtualDirectoryType Mailboxes -Name "exchange"

Boom.