A relationship is in the Deleted state

There is one trick. You can delete entities without using special DbSet:

(this.dataContext as IObjectContextAdapter).ObjectContext.DeleteObject(entity);

Execute this for each item in Availability collection before clearing it. You don't need 'identifying relationships' for this way.

The only way that I'm aware of to make it work is defining the relationship as an identifying relationship. It would required to introduce the foreign key from Availability to User as a foreign key into your model...

public int ID { get; set; }
public int UserID { get; set; }
public User User { get; set; }

...and make it part of the primary key:

modelBuilder.Entity<Availability>()
    .HasKey(a => new { a.ID, a.UserID });

You can extend your mapping to include this foreign key (just to be explicit, it isn't required because EF will recognize it by convention):

modelBuilder.Entity<Availability>()
    .HasRequired(a => a.User)
    .WithMany(u => u.Availability)
    .HasForeignKey(a => a.UserID);

(BTW: You need to configure the relationship only from one side. It is not required to have both these mappings in your question.)

Now you can clear the collection with user.Availability.Clear(); and the Availability entities will be deleted from the database.