Laravel 4 - how to use a unique validation rule / unique columns with soft deletes?
This sounds like an issue with your business logic rather than a technical problem.
The purpose of a soft delete is to allow for the possibility that the soft-deleted record may be restored in the future. However, if your application needs uniqueness of email (which is completely normal), you wouldn't want to both create a new user with that email address and be able to restore the old one as this would contravene the uniqueness requirement.
So if there is a soft deleted record with the email address for which you are adding as a new record, you should consider instead restoring the original record and applying the new information to it as an update, rather than trying to circumvent the uniqueness check to create a new record.