If they want to return to the auto attendant, they need to transfer from that mailbox. So either the "Personal Operator" for the mailbox needs to go to a mailbox that is set as the auto attendant, or they can dial *8 and then the mailbox number.
So take an unused extension, something simple, say 55 (if you have a Partner II or ACS R3 or later). Give if Auto VMS Cover in #310. Make its VMS Cover Rings 1 in #321. In the Partner Messaging, go to Extensions, 2, enter the extension number and pound, 55#, assign it to an auto attendant, 3, and then select which auto attendant, 1.
In the mailbox greeting, you would say something like "leave a message at the tone, or to return to the auto attendant, press *855"
Hope this helps.