Welcome to Android Central! Where are you seeing the deleted apps still appearing? Are you in the Data Usage menu? Data Usage will still show recent data use by deleted apps (although it should be listed as Deleted Apps). It doesn't mean those deleted apps are still using up your data plan.
No, not in the Data Usage. When I select Apps, I still the "Map" app, even though I deleted it from the Google apps. Also, I removed Gmail from the apps, and it still appeared in the Apps section. It took me a number of attempts to remove it.
I read somewhere else that even though you are not using the apps, they can use up data as they periodically try to sync with the parent site.
Google Maps and Gmail are often preinstalled apps that can't be completely uninstalled unless you root the device. When you tried to uninstall them, you might have just been uninstalling all of their updates, reverting them to the factory version of the apps.
Go to Settings>Apps>All, and select Google Maps or Gmail. Do you see an Uninstall button there, or only a Force Stop and Disable button?