Can anyone confirm for me that the User Profile to SharePoint Full Synchronization timer job must run in order to remove ophan ad users from a site collection? From my understanding this will remove the record from the profile database and then remove the user from the site collection's userinfo table.
A full synchronization is not needed to remove the entries from the User Profile database only a incremental followed by My Site Cleanup. See Account Deletion and SharePoint 2010 User Profile Synchronization
But this will not remove users from the Site collections userinfo table, there is no automatic deletion happening here. If you want to do the clean up you can use Clean-up User Information List