gistfile1.cs

public class CompanyService
{
	// ...
	public Delete(long companyId)
	{
		var company = GetById(companyId);
		company.DeletedAtUtc = DateTimeOffset.Now;
		database.Companies.Remove(company); // it's like we usually delete
		database.SaveChanges();
	}
}

public class Company
{
    [DatabaseGenerated(DatabaseGeneratedOption.Identity)]
    public long CompanyId { get; set; }
    public string Name { get; set; }
    public bool IsDeleted { get; set; }
    public DateTimeOffset? DeletedAtUtc { get; set; } // property added
}