DBのユニーク規制が、データの整合性を保つ最後の砦だと考えている。
実装に注意したり、DBを直接書き換える場合に、注意すれば良いのだけれど、やっぱりバグやヒューマンエラーは付き物。
バグやヒューマンエラーを考えると論理削除を使って、定期的にクリーニングがベストかな。

論理削除のGemを探しましたが、日付を使う物が多く、かつNULLが使われるので、複合キーでのユニーク規制が掛からない。
フラグを使う物もあったけど、0・1では一度削除したものと同じものを再度削除出来なくなる。
辿り着いたのは、初期値0で、削除時にIDと同じ値を設定するというDB設計。
ただ、これを満たすGemが見つからないので、良さそうなParanoiaの一部を修正する(モンキーパッチを充てる)事にしました。

また、JOINされるケースでSQLが「WHERE “.`deleted` = 0」となり、「Mysql2::Error: Column ‘deleted’ in where clause is ambiguous:」で落ちる問題も対応しました。
このバージョンの組み合わせだから動かない、という事なんだろうか？(謎)

前提：Rails 4、Paranoia 2.0.2

Paranoia追加

編集：Gemfile

# Use Paranoia
gem 'paranoia', '2.0.2' # モンキーパッチ：config/initializers/extensions/paranoia.rb

$ bundle install
===========================================
Installing paranoia 2.0.2
===========================================
※「Your bundle is complete!」と表示されればOK

Paranoiaカスタマイズ

作成：config/initializers/extensions/paranoia.rb

module Paranoia
  module Query
    def only_deleted
      # with_deleted.where.not(paranoia_column => nil)
      with_deleted.where.not(paranoia_column => 0)
    end
  end

  def restore!(opts = {})
    ActiveRecord::Base.transaction do
      run_callbacks(:restore) do
        # update_column paranoia_column, nil
        update_column paranoia_column, 0
        restore_associated_records if opts[:recursive]
      end
    end
  end

  private

  def touch_paranoia_column(with_transaction=false)
    if with_transaction
      # with_transaction_returning_status { touch(paranoia_column) }
      with_transaction_returning_status { update_attribute(paranoia_column, id) }
    else
      # touch(paranoia_column)
      update_attribute(paranoia_column, id)
    end
  end
end

class ActiveRecord::Base
  def self.acts_as_paranoid(options={})
    alias :really_destroy! :destroy
    alias :destroy! :destroy
    alias :delete! :delete
    include Paranoia
    class_attribute :paranoia_column

    # self.paranoia_column = options[:column] || :deleted_at
    self.paranoia_column = options[:column] || :deleted
    # default_scope { where(paranoia_column => nil) }
    def self.default_scope
      where(arel_table[paranoia_column].eq 0)
    end

    before_restore {
      self.class.notify_observers(:before_restore, self) if self.class.respond_to?(:notify_observers)
    }
    after_restore {
      self.class.notify_observers(:after_restore, self) if self.class.respond_to?(:notify_observers)
    }
  end
end

ベースモデル作成

$ rails g model base
===========================================
      invoke  active_record
      create    db/migrate/20140707233955_create_bases.rb
      create    app/models/base.rb
      invoke    rspec
      create      spec/models/base_spec.rb
      invoke      factory_girl
      create        spec/factories/bases.rb
===========================================
※エラーが表示されなければOK

削除：db/migrate/20140707233955_create_bases.rb
削除：spec/factories/bases.rb

編集：app/models/base.rb

class Base < ActiveRecord::Base
  self.abstract_class = true
  acts_as_paranoid
end

テストモデル作成

$ rails g model test
===========================================
      invoke  active_record
      create    db/migrate/20140707234352_create_tests.rb
      create    app/models/test.rb
      invoke    rspec
      create      spec/models/test_spec.rb
      invoke      factory_girl
      create        spec/factories/tests.rb
===========================================
※エラーが表示されなければOK

編集：db/migrate/20140707234352_create_tests.rb

class Tests < ActiveRecord::Migration
  def change
	create_table :tests do |t|
      t.string :name, null: false
      t.timestamps
      t.integer :deleted, null: false, default: 0
    end
    add_index :tests, [:name, :deleted], unique: true
  end
end

$ rake db:migrate
※エラーが表示されなければOK

編集：app/models/test.rb

class Test < ActiveRecord::Base
class Test < Base
end

動作確認

$ rails c

Test.create(name: 'test')
test = Test.find_by_name('test')
test.blank?
 => false
test.destroy
 => UPDATE文
test = Test.find_by_name('test')
test.blank?
 => true
exit

テストモデル削除

削除：app/models/test.rb
削除：db/migrate/20140707234352_create_tests.rb
削除：spec/models/test_spec.rb
削除：spec/factories/tests.rb

$ rake db:migrate:reset
※エラーが表示されなければOK