my deleted "to-dos" are showing up under the Task section of my recycle bin. To Victoria's point, Support should be able to walk you through this, as long as it's been 30 days or less. You can also potentially just do a quick screenshot of the Preview sandbox's to-do widget for the user and they can manually recreate their missing items, if all else fails.
(Also, since you were unable to locate it in your recycle bin, I would suggest you check the user's Personal Project just in case they were not deleted after all)