The solutions lays within the use of a set in which the keys of the items that needs to be deleted are stored. After the first iteration another iteration takes place to actually delete the applicable items from the map.

public Map cleanupRecordMap(Map _recordMap)
{
    MapIterator     recordIterator = new MapIterator(_recordMap);
    Set             deleteRecordSet = new Set(Types::String);
    SetEnumerator   deleteRecordSetEnumerator;
    ;

    if(_recordMap.elements() > 0)
    {
        while(recordIterator.more())
        {
            if(true)
            {
                // mark record to be deleted by adding it to a set
                deleteRecordSet.add(recordIterator.domainValue());
            }
            
            recordIterator.next();                                 
        }
                
        // use the set of keys to remove them from the map
        deleteRecordSetEnumerator = deleteRecordSet.getEnumerator();
        while(deleteRecordSetEnumerator.moveNext())
        {
            _recordMap.remove(deleteRecordSetEnumerator.current());   
        }
    }       

    return _recordMap;
}