Not able to choose "unsubscribe group" for a mailing?
What you describe is exactly what I observe at dmaster.demo.civicrm.org.

Steps

Run Search and select some contacts. 

Choose Email/Send via CiviMail



On the next screen I see the Unsub Group