That EWS based script is your best option here, as Search-Mailbox/eDiscovery cannot restore the deleted files directly in their original folders. You can of course also instruct the users to manually recover the items, depending on the type of tag you've configured that is.
To avoid any data loss, make sure to increase the Single-item recovery window to the maximum of 30 days and if you have the necessary licenses, put the mailboxes temporary on hold.
Thanks for this bit. I made significant progress with the EWS script. I am able to connect, find the items, and for the most part, recover them.
The one sticking point is - ideally, I would like to recover them to the folder that they were deleted from - including user created folders within the mailbox. I see the parentfolderid on the message - but it is some long crazy GUID or other unique identifier. I haven't yet been able to tie that to a folder in the mailbox -- am I headed in the right direction? Should that parentfolderid refer to the folder in which the message was deleted from?