I started with the code you posted, and ended up with the following:

Option Explicit
Public CmyLastRow As Long, CmyRange As String
Public CowListStart As Range, DeleteRange As Long

Private Sub cmdProblemDelete_Click()
Dim msg As String, DelRow As Long
'Make sure a cow ID has been selected.
If Me.cboCowList.ListIndex = -1 Then
MsgBox "You must select the cow ID to be deleted", vbExclamation,
"cmdProblemDelete_Click"
Exit Sub
End If
'Confirm the deletion.
msg$ = "Are you sure you want to delete cow " & Me.cboCowList.Value & "?"
If MsgBox(msg$, vbQuestion + vbYesNo, "Confirm Delete") = vbYes Then
'Delete the row for the selected  cow.
Worksheets("EnterCowData").Activate
'Since cow IDs are sorted and are in the same order as in the combobox, we can
calculate
'the correct row. ListIndex is the position of the selected item  in the comcobox
list. Since
'it begins numbering with zero, we must add 1. Also add 3 for the rows  above the
first cow.
DelRow& = (Me.cboCowList.ListIndex + 1) + 3
ActiveSheet.Cells(DelRow&, 1).EntireRow.Delete
'Reload the combobox.
Call LoadcboCowList
End If
End Sub

Private Sub LoadcboCowList()
'Call RangeSelection to sort the data and assign value to CmyLastRow.
Call RangeSelection
cboCowList.RowSource = "A4:A" & CmyLastRow
cboCowList.BoundColumn = 1
cboCowList.ColumnCount = 1
'No item selected, to start.
cboCowList.ListIndex = -1
End Sub

Private Sub RangeSelection()
'Finds the used range, sorts the data, and populates public variables.
Dim TmpAddr As String
Worksheets("EnterCowData").Activate
'Call FindLastCell function to get the address of the cell with the highest used
'column and highest used row on the selected sheet.
TmpAddr = FindLastCell(Worksheets("EnterCowData"))
'If FindLastCell returned "ERROR" the sheet is probably blank.
If TmpAddr$ = "ERROR" Then Exit Sub
'Assign the last used row to CmyLastRow
CmyLastRow = Range(TmpAddr$).Row
'Select all the cells from A3 through TempAddr
CmyRange = "A3:" & TmpAddr$
'Sort the range  by CowID
Range(CmyRange).Select
Selection.Sort Key1:=Range("A3"), Order1:=xlAscending, Header:=xlYes, _
OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, _
DataOption1:=xlSortNormal
End Sub

Private Sub UserForm_initialize()
Call LoadcboCowList
Application.ScreenUpdating = True
End Sub

Function FindLastCell(Wksht As Worksheet) As String
'Returns address of last cell used (highest row & col) on specified sheet
Dim LastRow As Long
Dim LastCol As Integer
On Error GoTo FLCerr1
With Wksht
LastRow = 0
LastCol = 0
LastRow& = _
.Cells.Find("*", after:=.Cells(1), _
LookIn:=xlFormulas, LookAt:=xlWhole, _
SearchDirection:=xlPrevious, _
SearchOrder:=xlByRows).Row
LastCol% = _
.Cells.Find("*", after:=.Cells(1), _
LookIn:=xlFormulas, LookAt:=xlWhole, _
SearchDirection:=xlPrevious, _
SearchOrder:=xlByColumns).Column
End With
FindLastCell$ = Cells(LastRow&, LastCol%).AddressLocal
Exit Function
FLCerr1:
FindLastCell$ = "ERROR"
End Function

I'm afraid I have altered it quite a bit, but it does work reliably now to
load cboCowList, delete the selected cow, and reload cboCowList.

If these changes interfere with something else in your project, let me know,
and i will be glad to help you.