has_friendly_id not working with acts_as_paranoid model

Question

I am getting following error while adding a record in my Contact model.

Mysql2::Error: Duplicate entry 'john-doe' for key 'index_contacts_on_cached_slug': UPDATE `contacts` SET `cached_slug` = 'john-doe', `company` = 'XYZ-company-name', `first_name` = 'John', `last_name` = 'Doe', `prefix` = NULL, `suffix` = NULL, `title` = NULL, `created_at` = '2012-04-07 06:25:37', `updated_at` = '2012-04-07 06:25:37', `deleted_at` = NULL WHERE `contacts`.`id` = 314

Contact model looks like

acts_as_paranoid

has_friendly_id :full_name, :use_slug => true, :approximate_ascii => true, :allow_nil => true,
    :sequence_separator => '_', :max_length => 20

Now the scenario is if a new Contact with similar name is added and existing contact is paranoid then friendly_id is unable to find that record and creates a new slug with similar name, but Contact model wont accept it as that slug name is already present.

Is there a way to make friendly_id consider the paranoid records as well i.e. use something like

scope => :with_deleted