First, make sure you actually deleted the plugin and did not just disable it.
Assuming that the plugin was deleted, one of the following could cause this:
Bad Cron Jobs
Some plugins will create cron jobs and not remove them when the plugin is disabled or deleted.
These can easily slow sites down if set up badly.
Check to see if the plugin created cron jobs and remove any found.
Do a quick search on this site for removing cron jobs and you will find what you need to track them down and remove them.
Extra Options
Check for theme options and post_meta options created by the plugin and delete them.
I doubt that this is the main problem as you have to add tons of options to really slow things down … but some plugins do so.
I cannot think of a lot of other things that could cause this kind of problem. Hopefully someone else can chime in here.