For the sake of completeness, here's what I ended up doing in order to correct the issue:
class Cellar < ActiveRecord::Base
belongs_to :house, dependent: :destroy
accepts_nested_attributes_for :house, allow_destroy: true
attr_accessible :house_id, :house_attributes, [...]
# I ADDED THIS:
before_save :drop_invalid_id
def drop_invalid_id
self.house_id = nil if house.marked_for_destruction?
end
end