Решил. Если коротко:
1. Завёл все метки в коллекцию, при добавлении записывая в отдельный массив какому элементу какой ID соответствует (начинаются с 0, увеличиваются на 1)
2. Добавил её на карту
3. При редактировании меток в коллекции (обращаясь к переменной коллекции, а не к переменной карты), изменения сразу отражаются на карте.
Например:
map_orgs.get(5).options.set('preset','islands#redIcon');
где map_orgs - название коллекции.
Здесь мы берём элемент коллекции с id=5 и меняем опцию preset.