Welcome to WebmasterWorld Guest from 22.214.171.124
You should verify the technical transition to a new URL structure no matter what (301s as appropriate, with no internal lnks going through a 301.)
watch out for what the third party SEO company is actually doing to generate 1-way links
Did you change domains?
You said you moved to a dedicated server from what? A vps?
Did page load times worsen or improved?
Any connectivity problems?
Did you change the dns settings?
You removed 2.5K of pages but you did not place 301 redirects to equivalent or nearest pages, since pages removed, were contributing to your site's rank and these requests are associated with your site's content.
Then you did various content and link changes, how did you validate those? Are you saying you paid somebody and he placed a ton of external links to your domain to improve SEO?