If a user deletes a message shell (stub) in Outlook will Archive Manager (AM) recreate it?
No. After being deleted the stub is permanently gone.
If they are required back in Exchange (Outlook) then the only way would to be to export the messages from Archive Manager to a PST then copy the messages from that PST back into the mailbox and allow AM to re-strip them therefore creating new stubbs.