I see. I think because I first take index 0 and delete that one. Then everything shifts one up...
Maybe enumerate first to get the highest index and then count back to 0.
Code:
If NOT @LOGONMODE
	Break On
Else
	Break Off
EndIf
Dim $RC
$RC=SetOption("Explicit", "On")
$RC=SetOption("NoMacrosInStrings", "On")
$RC=SetOption("NoVarsInStrings", "On")
$RC=SetOption("WrapAtEOL", "On")

Dim $Ptr, $index, $OldServer
$index = 0
$OldServer = "OldServer"

$Ptr = EnumKey("HKCU\Printers\Connections\",$index)
While NOT @ERROR
	;"Printer with index " + $index + ": " + $Ptr ?
	$index = $index + 1
	$Ptr = EnumKey("HKCU\Printers\Connections\",$index)
Loop

If 0 < $index
	$index = $index - 1
	Do
		$Ptr = EnumKey("HKCU\Printers\Connections\",$index)
		If InStr($Ptr,$OldServer)
			;"KeyName to delete: " + "HKCU\Printers\Connections\" + $Ptr + "\" ?
			$RC = DelKey("HKCU\Printers\Connections\" + $Ptr + "\")
		EndIf		
		$index = $index - 1
	Until 0 > $index
EndIf