Then it's normal for XP to complain if you have such a small hard disk and so little free space. After removing programs, did you delete the folders where they were installed? Removing a program doesn't always completely clean up the folders.
If you don't plan on uninstalling Microsoft patches, you can delete a bunch of hidden folders in C:\Windows, e.g., $NtUninstallKB898461$. Just make sure they are patches that will never be uninstalled and not applications. Any folder that starts with $NtUninstallKB is pretty safe to delete (you can always restore them from a full system backup).
This might help if you have lots of restore points: http://www.lockergnome.com/windows/2005/04/12/delete-system-restore-points-to-free-disk-space/
Can't you get a larger hard disk?