THE SHORT VERSION - make sure the VRDE IP address stored in the VM is the same as the virtualbox host!
Ok, so I had a VM that I used to be able to connect to remotely using rdesktop then but then one day I was no longer able to connect.
When starting the VM headlessly using:
VBoxHeadless --startvm XP
I got the error:
Oracle VM VirtualBox Headless Interface 4.1.22
(C) 2008-2012 Oracle Corporation
All rights reserved.

VRDE server failed to start.
VRDE server is inactive.
The log file for this VM looks like this:
chris@chris:~/.VirtualBox/Machines/XP/Logs$ more VBox.log
VirtualBox 4.1.22 r80657 linux.amd64 (Sep  7 2012 17:37:29) release log
00:00:00.426 Log opened 2012-10-11T13:14:51.600242000Z
00:00:00.426 OS Product: Linux
00:00:00.426 OS Release: 2.6.32-5-amd64
00:00:00.426 OS Version: #1 SMP Sun Sep 23 10:07:46 UTC 2012
00:00:00.426 DMI Product Version: ThinkStation S20
00:00:00.427 Host RAM: 5979MB RAM, available: 5258MB
00:00:00.427 Executable: /usr/lib/virtualbox/VBoxHeadless
00:00:00.427 Process ID: 24851
00:00:00.427 Package type: LINUX_64BITS_DEBIAN_6_0
00:00:00.434 Installed Extension Packs:
00:00:00.434   Oracle VM VirtualBox Extension Pack (Version: 4.1.22 r80657; VRDE Module: VBoxVRDP)
00:00:00.437 VRDP: Statistics created: [full], enabled: 0.
00:00:00.437 VRDP: VRDP: VD: Frames=10 MinMS=15 MaxMS=300 HistoryMS=2000 VideoMS=300
00:00:00.441 VRDP: TCP server failed to bind to a port: 3389 [4000]
00:00:00.441 VRDP: TCP server closed.
00:00:00.441 VRDP: Failed to start VRDP-IN thread, rc = VERR_NET_ADDRESS_IN_USE
00:00:00.441 VRDE: Warning: failed to launch VRDE server (VERR_NET_ADDRESS_IN_USE): 'VirtualBox Remote Desktop Extension server can't bind to the port: 4000',
All looks normal, it will try and start the headless VM on port 4000 and netstat shows that port is unused.
The penny dropped when I checked the VM info:
VBoxManage showvminfo XP | grep VRDE
VRDE:            enabled (Address, Ports 4000, MultiConn: off, ReuseSingleConn: off, Authentication type: null)
VRDE property: TCP/Ports  = "4000"
VRDE property: TCP/Address = ""
VRDE property: VideoChannel/Enabled = <not set>
VRDE property: VideoChannel/Quality = <not set>
VRDE property: VideoChannel/DownscaleProtection = <not set>
VRDE property: Client/DisableDisplay = <not set>
VRDE property: Client/DisableInput = <not set>
VRDE property: Client/DisableAudio = <not set>
VRDE property: Client/DisableUSB = <not set>
VRDE property: Client/DisableClipboard = <not set>
VRDE property: Client/DisableUpstreamAudio = <not set>
VRDE property: Client/DisableRDPDR = <not set>
VRDE property: H3DRedirect/Enabled = <not set>
VRDE property: Security/Method = <not set>
VRDE property: Security/ServerCertificate = <not set>
VRDE property: Security/ServerPrivateKey = <not set>
VRDE property: Security/CACertificate = <not set>
VRDE property: Audio/RateCorrectionMode = <not set>
VRDE Connection:    not active
This showed the IP address for VRDE is stored within the VM and the IP of the VBox host had changed, causing this error!
Changing the VM's VRDE IP address fixed the problem:
VBoxManage modifyvm XP --vrdeaddress