I might be trivializing this but you could create a view "ActiveUsers" / "DeletedUsers". Not saying this make the IsDeleted flag perfect, but it would alleviate that particular problem, IMO.