PPTP connection fails with errors 800/806

I've got a client (Server 2008 R2) that won't connect to our production environment PPTP VPN server (Server 2003, running RRAS).

The server is behind a firewall that has TCP1723 open as well as GRE. Other clients at our office are able to connect just fine. Our office is behind a Juniper SSG5-Serial firewall, but all outgoing traffic is allowed, and multiple other clients are able to connect to VPN servers without issues.

I've also setup a completely different VPN server on another network outside of our office. The functioning clients connect just fine - the Server 2008 R2 machine doesn't. Thus it's definitely a problem with this machine in particular.

I've rebooted it. I've disabled the firewall, no dice on either.

I've run PPTPSRV and PPTPCLNT on the server/client and they're able to communicate perfectly - indicating there's no problem using neither TCP1723 nor GRE.

The Server 2008 R2 machine is also running as a VPN server itself (incoming connection) and that's working perfectly. We have the issues no matter if there are active incoming connections or not.

I'm not sure what my next debugging step would be; any suggestions?

EDIT: The event log on the server has the following warning from RasMan:

A connection between the VPN server and the VPN client xxx.xxx.xxx.xxx has been 
established, but the VPN connection cannot be completed. The most common cause
for this is that a firewall or router between the VPN server and the VPN client
is not configured to allow Generic Routing Encapsulation (GRE) packets (protocol 47).
Verify that the firewalls and routers between your VPN server and the Internet allow
GRE packets. Make sure the firewalls and routers on the user's network are also
configured to allow GRE packets. If the problem persists, have the user contact
the Internet service provider (ISP) to determine whether the ISP might be blocking
GRE packets.

Obviously this points to GRE being a potential problem. But seeing as I have other clients connectiong without problems, as well as PPTPSRV and PPTPCLNT being able to communicate, I'm suspecting this might be a red herring.

EDIT: Here are the anonymized events logged by the client in chronological order:

CoId={742CB15C-A7E0-47B7-8240-0EFA1139CBD9}: The user XXX\YYY has started dialing a VPN connection using a per-user connection profile named ZZZ. The connection settings are: 
Dial-in User = XXX\YYY
VpnStrategy = PPTP
DataEncryption = Require
PrerequisiteEntry = 
AutoLogon = No
UseRasCredentials = Yes
Authentication Type = CHAP/MS-CHAPv2 
Ipv4DefaultGateway = No
Ipv4AddressAssignment = By Server
Ipv4DNSServerAssignment = By Server
Ipv6DefaultGateway = Yes
Ipv6AddressAssignment = By Server
Ipv6DNSServerAssignment = By Server
IpDnsFlags = Register primary domain suffix
IpNBTEnabled = Yes
UseFlags = Private Connection
ConnectOnWinlogon = No.

CoId={742CB15C-A7E0-47B7-8240-0EFA1139CBD9}: The user XXX\YYY is trying to establish a link to the Remote Access Server for the connection named ZZZ using the following device: 
Server address/Phone Number = XXX.YYY.ZZZ.KKK
Device = WAN Miniport (PPTP)
Port = VPN3-4
MediaType = VPN.

CoId={742CB15C-A7E0-47B7-8240-0EFA1139CBD9}: The user XXX\YYY has successfully established a link to the Remote Access Server using the following device: 
Server address/Phone Number = XXX.YYY.ZZZ.KKK
Device = WAN Miniport (PPTP)
Port = VPN3-4
MediaType = VPN.

CoId={742CB15C-A7E0-47B7-8240-0EFA1139CBD9}: The link to the Remote Access Server has been established by user XXX\YYY.

CoId={742CB15C-A7E0-47B7-8240-0EFA1139CBD9}: The user XXX\YYY dialed a connection named ZZZ which has failed. The error code returned on failure is 806.

Running Wireshark on the client shows it trying and retrying to send a "71 Configuration Request"

While the server shows the incoming client requests, but apparently without replying:

Given that this is GRE traffic, I think rules out the GRE traffic being blocked. Question is, why doesn't the server reply?

This is the Configuration Request the server receives from the non functioning client (meaning no response is sent to the client request):

And this is the Configuration Request the server receives from the working client:

To me they seem identical, except for differing keys and magic numbers, and the fact that one client receives a response while the other doesn't.