Does anyone know of any way off of any platform (Exchange
Server, Outlook, ADO, CDO, etc) to programmatically access
the "Recover Deleted Items" entries that exist in Outlook
menus?

I'm NOT talking about the Deleted Items folder but rather
the menu item that is enabled when you are on the Deleted
Items folder.  Using Outlook 2000 against an Exchange 5.5
server, I select the Deleted Items folder then select
Tools/Options/Recover Deleted Items.  These are generally
Exchanged "tombstoned" items that our server has been
configured to keep for 2 weeks.