Tested on Mongoid 3.1.4.

class Foo
include Mongoid::Document
include Mongoid::Paranoia
field :bar, type: String
validates_uniqueness_of :bar
end

baz = Foo.create(bar: 'qux')

MOPED: 127.0.0.1:27017 QUERY database=gocheap_development collection=foos selector=

{"deleted_at"=>nil, "bar"=>"qux"} flags=[] limit=1 skip=0 batch_size=nil fields={:_id=>1} (0.4134ms)
MOPED: 127.0.0.1:27017 INSERT database=gocheap_development collection=foos documents=[{"_id"=>"51b1f9355b9e052597000015", "bar"=>"qux"}] flags=[] (0.2580ms)
#<Foo _id: 51b1f9355b9e052597000015, deleted_at: nil, bar: "qux">

>> baz.destroy
MOPED: 127.0.0.1:27017 UPDATE database=gocheap_development collection=foos selector={"_id"=>"51b1f9355b9e052597000015"} update={"$set"=>{"deleted_at"=>2013-06-07 22:16:17 +0700}} flags=[] (0.2680ms)
true

>> quux = Foo.create(bar: 'qux')
MOPED: 127.0.0.1:27017 QUERY database=gocheap_development collection=foos selector={"deleted_at"=>nil, "bar"=>"qux"}

flags=[] limit=1 skip=0 batch_size=nil fields={:_id=>1} (0.7606ms)
MOPED: 127.0.0.1:27017 INSERT database=gocheap_development collection=foos documents=[

{"_id"=>"51b1f9545b9e052597000016", "bar"=>"qux"}

] flags=[] (0.4735ms)
#<Foo _id: 51b1f9545b9e052597000016, deleted_at: nil, bar: "qux">

So it successfully creates despite the fact, that there is a record with the same 'bar' value in the collection because it searches with deleted_at: nil. I think, that this behaviour is wrong, because if we want to take into account the deleted_at field, we can just add it as a scope to the uniqueness validation. And there are bugs with the current behaviour:

>> baz.restore
MOPED: 127.0.0.1:27017 COMMAND database=admin command={:ismaster=>1} (0.6130ms)
MOPED: 127.0.0.1:27017 UPDATE database=gocheap_development collection=foos selector=

{"_id"=>"51b1f9355b9e052597000015"} update={"$unset"=>{"deleted_at"=>true}} flags=[] (0.5136ms)
true

Great, now we have two active objects with the same 'bar' value.

Also:

>> baz.destroy
MOPED: 127.0.0.1:27017 UPDATE database=gocheap_development collection=foos selector={"_id"=>"51b1f9355b9e052597000015"}

update={"$set"=>{"deleted_at"=>2013-06-07 22:26:01 +0700}} flags=[] (0.2160ms)
true

>> baz.valid?
true

>> baz.bar
"qux"

>> baz.bar = 'temp'
"temp"

>> baz.save
MOPED: 127.0.0.1:27017 QUERY database=gocheap_development collection=foos selector=

{"deleted_at"=>nil, "bar"=>"temp"}

flags=[] limit=1 skip=0 batch_size=nil fields={:_id=>1} (0.7241ms)
true

>> baz.bar = 'qux'
"qux"

>> baz.save
MOPED: 127.0.0.1:27017 QUERY database=gocheap_development collection=foos selector=

{"deleted_at"=>nil, "bar"=>"qux"} flags=[] limit=1 skip=0 batch_size=nil fields={:_id=>1} (0.6340ms)
false

>> baz.valid?
MOPED: 127.0.0.1:27017 QUERY database=gocheap_development collection=foos selector={"deleted_at"=>nil, "bar"=>"qux"}

flags=[] limit=1 skip=0 batch_size=nil fields={:_id=>1} (0.4935ms)
false

So we changed the field and then returned its value, and this made the record invalid.