Prevent undelete

You can use addError on records in the after undelete trigger event, and it will prevent the record from being recovered.

You need a fairly simple Apex Trigger:

trigger MyObject on My_Object__c (after undelete)
{
    for (My_Object__c record : trigger.new)
        record.addError(Label.Undelete_Not_Allowed);
}

I recommend using a Custom Label for your error message because they are configurable and hence can be changed on the fly.

---

I did check to see if this functionality can be performed via Validation Rule, but the field IsDeleted cannot be used in one. Otherwise, you could use the following formula:

PRIORVALUE(IsDeleted, true)