I really want to accept @Waqas answer as that answer and the very long discussion in the comments are things that should have worked. But, ultimately, they didn't.
I was able get the id and stop the Application Discovery and Load Balancer Service Application by running:
Get-SPServiceInstance -all | out-file c:\servicelistall.txt
And
stop-spserviceinstance <id as located from output in previous command>
I had to run this on each server in our farm. Despite this, when I tried:
remove-SPManagedAccount -Identity <domain\networkid>
I got an error that said a user by that name could not be found. This annoyed the tar out of me because running gET-SPManagedAccountclearly showed the managed account.
As I had thought all along, we had really shot ourselves in the foot by 1) using a user account in the farm in the first place 2) deleting said domain account before reassigning it's responsibilities. Oops. Yay!
Given that all of the user facing options SharePoint exposes either through Central Administration or through PowerShell had failed, I was left with only one option that I saw: locate the managed account in the config database and update the record.
I found the managed users via:
SELECT TOP 10000 [Id]
,[ClassId]
,[ParentId]
,[Name]
,[Status]
,[Version]
,[Properties]
FROM [SharePoint_Config].[dbo].[Objects]
where len(name) > 0 and name is not null
and name like '%managed%'
From here I was able to locate the specific records via:
SELECT TOP 10000 [Id]
,[ClassId]
,[ParentId]
,[Name]
,[Status]
,[Version]
,[Properties]
FROM [SharePoint_Config].[dbo].[Objects]
where len(name) > 0 and name is not null
and name like '%managed%'
and properties like '%<domain account here>%'
The solution at this point can go a couple of ways but they all amount to updating the target record in the objects table with an m_SID (note that this is a field in the xml of the properties value) value that exists in AD. In our case, we recreated the missing account, but that didn't work because the m_SID value didn't match the one in SharePoint.
After getting the m_SID for the new account, I did an update on the name & properties fields.
After that everything worked fine in SharePoint. I was able to go Central Administration --> Security --> Configure Service Accounts (remember this page bombed before hand) and reassign the Application Discovery and Load Balancer Service Application to the farm account and subsequently delete the managed account that was no longer used.
I have spent a number of days trying to resolve this. Thank you, Waqas Sarwar MCSE, for helping me exhaust all the SharePoint & PowerShell options I didn't know existed.
Lastly, I really want to point the reader to: Replace a managed account in SharePoint. This script was magnificent resource and aided me in replacing this account in other places. For whatever reason, it was not picking up the Application Discovery and Load Balancer Service Application service, even after adding the -all flag to the Get-SPServiceInstance calls. As with any script you didn't write yourself, read it over, understand what it does, and probably comment out the bits that actually change stuff so you can see what all would be changed via the Write-Host outputs (may need to add some as needed).
