Если планируется одновременная работа с данными, да ещё и их изменение, то лучше рассмотреть вопрос с БД.
Есть много вариантов простых встроенных в программу движков, которые обеспечат вам корректную одновременную работу с данными.
Если же хочется поиграться самому, то вот несколько моментов.
Для одновременной работы из нескольких потоков файл нужно открывать с опциями FileShare.Read или FileShare.ReadWrite. Особенности работы с ними прочитаете сами.
Удаление данных в начале файла приводит к его полному переписыванию операционной системой. То есть компьютер всё равно прочтёт 600 МБ, просто это будет не в вашем потоке.
Достаточно быстро просто помечать "удалённые строки" какими-то спецсимволами. Например, вы можете выделить под это первый символ строки. А очистку начала файла производить раз в 100-200-300-500 "удалений".
При этом, если вы планируете многопоточность, то нужно хорошо организовать их взаимодействие, а то получите дважды обработанные строки.