This is a well-known issue. Iterators are not reliable when you modify the underlying collection while using the iterator.
As for the behavior you experience:
With CPython, the list iterator is represented by an index into the array. If you remove an item from the list at the iterator position or before it while still iterating over it, the iterator jumps forward. The iterator position index is still the same, but all items "under" the iterator have just moved to the left by one position. This makes the iterator skip one element. Hence you only remove every second item.
l = [1, 2, 3, 4]
^it(pos=1)
l.remove(2)
l = [1, 3, 4]
^it(pos=1)
it.next() # automatically at the end of each for loop
l = [1, 3, 4] # we just skipped over an item
^it(pos=2)
Here's a nice little treatise on the topic from @mgiuca.
Interestingly enough, removing items after the iterator position is safe with the current implementation.
In short: don't modify collections while iterating over them. Alternatives for lists: Remove items from a list while iterating in Python