Slow loading frequent 404 errors from admin end – tried everything!

I’ve had my WordPress site running for about 18 months and, other than the first month when I was uploading a lot of content, everything has stayed the same in terms of pages, plugins and theme. All I’ve done is update WordPress and plugins when needed.

Since July, though, my site has become insanely slow, with the majority of the wait time seemingly just on connecting to the server (just getting to the login page takes about 20 seconds). I don’t have problems with any other sites. Also, when trying to work on my site, I was getting internal server error messages about 50% of the time. The hosting company replaced the .htaccess file and now those errors have been replaced, with the same frequency, by 404 errors. Whether updating a page, viewing the page list, updating a plugin – anything – half the time the wait results in a 404 error.

I have…
*Deleted unused plugins, deactivated others
*Tried the W3 Total Cache plugin (the hosting company tried to blame that for causing the problem, even though I’d installed it BECAUSE of the problem!)
*Tried the NextGEN Optimizer plugin for my gallery
*Reduced the number and size of images on the home page
*Increased the memory in the wp-config file to 1024
*The hosting company has increased the memory to 1024 in the php.ini file
*Repaired and optimised the database

Despite trying all this, there has been no improvement. Nothing about my site has changed in well over a year, yet the hosting company can’t/won’t pinpoint anything that happened their end in July to suddenly cause these frequent 404 errors and terrible slow loading that I’ve experienced from then onwards.

I suggested a problem with scripts being killed off prematurely, but the hosting company reckons that the memory increase should have stopped all that. Surely no WordPress site should require 1024mb memory anyway? Regardless, my site had been working just fine without increased memory until July, so I don’t see how these problems can have been caused my end when I’d made no changes.

I’d be grateful to hear any other suggestions that might not yet have been tried.