Yes I am have "retVal = oUDT.MoveFirst() " in script.  I failed to include in paste to post.

How are you opening the UDT?

Full Script:

retVal = 0 : ocsVal = "" : Counter = 0 : oUDT = 0 : Via = ""

if oSession.Updating = 0 and oSession.StartProgram = "SO_SALESORDER_UI" then
oUDT = oSession.GetObject("CM_UDTMaint_bus", "SO_UDT_SHIP_ACTIVE")
SET oUDT = oSession.AsObject(oUDT)

ocsVal = oScript.DebugPrint("Purging Lookup Records using purge script")

' Reinitialize UDT first
retVal = oUDT.MoveFirst()
ocsVal = oScript.DebugPrint("retVal on MoveFirst: " & retVal & "/" & oUDT.LastErrorMsg)
ocsVal = oScript.DebugPrint("oUDT.Eof: " & oUDT.Eof)
retVal = oUDT.GetValue("UDF_SHIP_VIA$",Via)
ocsVal = oScript.DebugPrint("Via: " & Via)

Do until oUDT.Eof = 1
if Via <> "" then
Counter = Counter +1
ocsVal = oScript.DebugPrint("UDT Delete Count: " & Counter)
ocsVal = oScript.DebugPrint("Via: " & Via)
retVal = oUDT.Delete()
end if
retVal = oUDT.MoveNext()
Loop
end if

It could be permissions.  I always check for access when creating new objects in a script.  Example:

oSequenceTable = oSession.GetObject("CM_UDTMaint_bus", "SO_UDT_SEQUENCE")
if oSequenceTable <> 0 then
	Set oSequenceTable = oSession.AsObject(oSequenceTable)
else	
	retVal = oSession.AsObject(oSession.UI).MessageBox("", "Access to SO_UDT_SEQUENCE is required for the ??? script to work.")
	exit sub
end if

No change.  3 records exist in the table but the trace is:

SCRIPT/CallScript - RefCount:01 Class:SO_SalesOrder_UI Proc:PostloadPADDRESS **
Purging Lookup Records using purge script
retVal on MoveFirst: 0/The file is empty or does not match filter.
oUDT.Eof: 1
Via:

No change.  3 records exist in the table but the trace is:

SCRIPT/CallScript - RefCount:01 Class:SO_SalesOrder_UI Proc:PostloadPADDRESS **
Purging Lookup Records using purge script
retVal on MoveFirst: 0/The file is empty or does not match filter.
oUDT.Eof: 1
Via:

I'm out of ideas, other than to check that your data is in the same company code you are using for testing.

I was able to resolve.  Instead of Move First, Eof and MoveNext, I changed to Move Last, Bof and MovePrevious.  

Look for a null / blank record in the table.  That is known to cause weird things.

My teammate gave me the same recommendation.  Looking at the data in the UDT, no blank records existed.  However, when opening with the lookup, one does exist.  How do I prevent resolve that issue?

Look at the data using DFDM... that is the sure way to know.