Solution: enumerate the BodyParts and look for BodyParts with a filename: this includes all the attachments and embedded images. The syntax is a little tricky, but BodyParts work just the same as Attachments.
Dim bodypart_count = Msg.BodyPart.BodyParts.Count
Dim i As Integer = 0
For i = 1 To bodypart_count
If Msg.BodyPart.BodyParts(i).FileName <> "" Then
attachment_count += 1
End If
Next