Well...let's understand that there are two different reflections of an operating system.
a. One is the boot options presented at login...which may or may present actual installed O/Ses.
b. The other is the actual installed O/S resident on a given partition.
It seems to me that you are telling us that you had two O/Ses installed....deleted the partition which one of those was one...yet you still see that you have two O/Ses to choose from when you initially boot.
This happens and is easily taken care of. Try the following: Removing the invalid entries from Boot.ini - http://windowsxp.mvps.org/bootopt.htm