Is there a way to auto "put back" everything in Trash?
If "Put Back" is disabled for a multiple-item selection it means that (at least) one of the items selected doesn't have its original location information stored in the Trash directory's .DS_Store file.  

Though it's less than ideal, try multi-selecting subsets of the files looking for groups that you can "Put Back" en masse before resorting to manual filing for the remaining files.