Se la lista contiene un item, ma...

[eziogsv]

Se mentre esegui un ciclo For Each elimini un elemento è normale che ottieni un errore, perché il numero di elementi cambia in corso di esecuzione.

Ma tu non hai bisogno di eliminarlo, ma SOLO di sostituirlo:

Dim Bool as Boolean
For x as Integer = 0 to My.Settings.storico.count - 1

   if My.Settings.Storico(x).Contains(PREFISSO) Then
      Bool = True
      My.Settings.Storico(x)= PREFISSO & " | " & Now
   End If

Next

If Not Bool Then ........