Yes this will happen because when you remove an item the listindex of all items which come after will change by 1 So if you remove item 5 of 10 then what was item 6 becomes item 5 and there is no item 10, since your code will go on to 6 you will be skipping over item 6 which is now 5 and so on.

The simple way is to start at the other end of the list and work backwards avoiding these issues.

Code:
Dim i
For i = lstSong.ListItems.Count to 1 Step -1
 If lstSong.ListItems.Item(i).ListSubItems.Item(4).Text <> lstGenre.List(lstGenre.ListIndex) Then
  lstSong.ListItems.Remove i
 End If
Next i