Recomiende el uso de la tabla temporal o la variable de tabla en Entity Framework 4. Actualice el marco de Performance Entity

Para volúmenes de datos como 300k filas, me olvidaría de EF. Haría esto teniendo una tabla como:

BatchId  RowId

Donde RowId es el PK de la fila que queremos actualizar, y BatchId solo se refiere a esta "ejecución" de 300k filas (para permitir varias a la vez, etc.).

Generaría un nuevo BatchId (esto podría ser cualquier cosa única, me viene a la mente Guid) y usaría SqlBulkCopy para insertar los registros en esta tabla, es decir,

100034   17
100034   22
...
100034   134556

Luego usaría un sproc simple para unir y actualizar (y eliminar el lote de la tabla).

SqlBulkCopy es la forma más rápida de llevar este volumen de datos al servidor; no te ahogarás en viajes de ida y vuelta. EF está orientado a objetos:es bueno para muchos escenarios, pero no para este.