Having searched the EE Knowledge Base, I have only found one other reference to someone else experiencing a 'Low on Registry Space' message in XP SP3.
I don't know if it's related, or just a coincidence, but my troubles started after contracting a rootkit trojan (and others).
I have tried all sorts of registry defrags and clean ups, including NTREGOPT, and CleanMyPC Registry Cleaner.
I have also run various trojan removal programmes, including Trojan Remover, Malwarebytes and TDSSKiller from Kaspersky.
If I Defrag my registry, I can get it down from approx 124Mb to 106Mb, but upon rebooting, it's back up. It sounds pretty massive for a registry, though, surely?
I have also run RegSeeker, which found a lot, but the registry only went from 106Mb to 104Mb.
I have also moved my paging file from C: to another drive, in the hope this would help (from what I read elsewhere), but to no avail.