I believe that when you use the Set keyword in VBA, it creates a pointer in the background to the worksheet's Range object in the worksheet you specified (each cell being an object in the collection of Cells of the Worksheet for a given Range). When the range is deleted while you are still referencing it in memory, the memory for the object that the Range variable was pointing to has been deallocated.
However, your Range variable most-likely still contains the pointer to the recently removed Range object, which is why it isn't nothing, but whatever it's pointing to doesn't exist anymore, which causes problems when you try to use the variable again.
Check out this code to see what I mean:
Public Sub test2()
Dim r As Excel.Range
Debug.Print ObjPtr(r) ' 0
Set r = ActiveSheet.Range("A1")
Debug.Print ObjPtr(r) ' some address
r.Value = "Hello"
r.Delete
Debug.Print ObjPtr(r) ' same address as before
End Sub
Check out this article for more info about ObjPtr():
http://support.microsoft.com/kb/199824
So while you have a valid address to an object, unfortunately the object doesn't exist anymore since it has been deleted. And it appears that "Is Nothing" just checks for an address in the pointer (which I think VBA believes that the variable is "Set").
As to how to get around this problem, unfortunately I don't see a clean way of doing it at the moment (if anyone does find an elegant way to handle this, please post it!). You can use On Error Resume Next like so:
Public Sub test3()
Dim r As Excel.Range
Debug.Print ObjPtr(r) ' 0
Set r = ActiveSheet.Range("A1")
Debug.Print ObjPtr(r) ' some address
r.Value = "Hello"
r.Delete
Debug.Print ObjPtr(r) ' same address as before
On Error Resume Next
Debug.Print r.Value
If (Err.Number <> 0) Then
Debug.Print "We have a problem here..."; Err.Number; Err.Description
End If
On Error GoTo 0
End Sub