JS>Проблема с многозадачностью есть и при добавлении, и при удалении, причем, независимо от того, кто будет удалять.
А почему бы не воспользоваться примитивами синхронизации OS? Типа мьютексы?