Even though you deleted an application pool in IIS, sometimes SharePoint doesn’t seem to care. I recently had some trouble setting up the user profile service, and needed to delete the UPS because of some misconfiguration. When I wanted to recreate the application pool I got an error, stating the application already exists.
But what when I can’t see this app-pool in IIS? Well PowerShell to the rescue:
Remove-SPServiceApplicationPool [AppPoolName]
This is almost to easy to be true.
BTW: when deleting the UPS (the service application), the application pool does not get deleted in IIS. This is extremely ugly, especially since the app-pool name is just some guid. When re-creating the service-application using the same settings as before (especially the same app pool name), this fails, because the name of the app-pool and the corresponding guid name for IIS seems to be stored in the configuration database.