I didn't know this about Giuliani either. Looks like he really is doomed if he ever tries to run in 2008. His critics will just add this to the ones about him being a RINO.
I don't think Guiliani is a RINO. He's too socially liberal to win the Republican primaries and his oppositon to the partial-birth abortion ban are sickening even to a social moderate as myself. However, he is a legitimate fiscal conservative and takes the Republican position on law and order issues. He's a true Republican who disagrees with the party line on abortion and gay marriage which are not litmus issues to who is a "real" Republican and who is a RINO.