Removing profile settings from a profile that no longer exists
My best tip would probably be to install the app again, with the profile and all of that, and then remove the profile again, then deleting the app and see if that helps.

It's hard to tell what might be causing the problem – you're sure there are no proxy settings in place anywhere and that the profile is deleted?

Edit: It seems there are some ghost settings you're unable to change. Your best chance would be to reset all the network settings (Settings -> General -> Reset -> Reset Network Settings), or restoring your iPhone to factory settings.