В Entity Framework 4, который является частью .NET 4.0, есть метод для ObjectContext
ExecuteStoredCommand (строка cmdText, параметры объекта [])
Это позволяет выполнять операции на основе набора непосредственно с вашим хранилищем данных.
В вашем примере вы могли бы сделать что-то вроде:
db.ExecuteStoreCommand("DELETE FROM [User] WHERE Sex = '{0}'", new[] {"girl"});