Hey guys thanks for the replies. When I got in touch with my host they were really no help with this. I've had my account with them for about two years now and over the time I had put up a ton of apps to test and tweak but eventually lost interest.
Now, looking over a lot of the stuff that I had installed I could see there were a lot of open threats. phpBB installs not up to date, indexes missing, poor folder structures, etc.
What it came down to was an upload script I was developing to use with a private forum. The image upload function didn't have any sort of checks on the files and the attacker managed to upload a copy of nstView which was then used to compromise the rest of the site.
Along with the steps above, I deleted all my old files that were not being used. I cleared old databases, as well as users that weren't in use. Sub domains and redirects were next, emails addresses and other logins came after that.
Lesson learned from this would be to treat my online files as if they were on my computer. They're much more open "online" which makes it even more important to stay on top of things. Thanks for the feedback.