From the web UI, under Recordings > Recordings > Trash, each deleted program has a "Recover" and "Delete Now" button. If you press "Recover", the program is added back to the database, and will appear in the clients as if nothing happened. If you press "Delete Now", it will function just like deleting a recording used to work.
The Trash feature does not delete the program immediately; it is left in place.
I believe the above question about adding deleted metadata back into the database was in reference to adding programs back using the "Import" feature, not when using "Restore" on a recording in the Trash.