Setup Exchange Online with AD Connect. Have Exchange 2003 Remnents in AD

Hey EWMiller79 

Assuming that you longer can trace the exchange 2003 server/management tools and aren't able to launch system manager connected to exchange server, You will have to use ADSIEDT to delete traces of exchange server, though not recommended by MS but its the only option you have given the situation. Assuming that you dont have any other exchange servers in the infra, its is relatively safer to delete server objects related to exchange using ADSIEDIT, On a high level the process would somewhat look like this: 

Via ADSIEDIT navigate to 

Configuration Container
CN=Configuration, DC=Domainname,DC=com
CN=Services
CN=Microsoft Exchange
CN=Your_Organization_Name
CN=Administrative Groups
CN=AdminstrativeGroup_Name
CN=Servers
Right click on the exchange 2003 object and delete the same.

Refer below article for more details:

https://www.alitajran.com/how-to-remove-exchange-from-active-directory/

The article was written w.r.t exchange 2016 and you may not find exact same objects in AD but whatever you can find based on the article you can delete.

That being said, even after removing the traces of exchange server, exchange related attributes still wont clean up automatically from users. First check against users in 'active directory users and computers' to see what exchange related attributes are populated, further you can use a script to clear out exchange related attributes, somewhat like this:

for a single user, using active directory powershell module:

set-aduser "SAMaccountName" -clear msExchMailboxGuid,msexchhomeservername,legacyexchangedn,msexchmailboxsecuritydescriptor,msexchpoliciesincluded,msexchrecipientdisplaytype,msexchrecipienttypedetails,msexchumdtmfmap,msexchuseraccountcontrol,msexchversion

Once again the attributes listed above are for recent versions of exchange, check whatever exchange related attributes you can find in AD and modify the script to clear targetted attributes. Once done try to force a full sync and check user's status in office 365. AADconnect re-installation may not be required.

Post testing and finalizing the attributes you wish to remove, you can run something like this for all users:

$users=Get-content c:\users.txt
Foreach($user in $users){
get-aduser $user| set-aduser -clear msExchMailboxGuid,msexchhomeservername,legacyexchangedn,msexchmailboxsecuritydescriptor,msexchpoliciesincluded,msexchrecipientdisplaytype,msexchrecipienttypedetails,msexchumdtmfmap,msexchuseraccountcontrol,msexchversion
}

Txt file contains SAM names for users you wish to target.

Thanks