Shared hosting blues? Or is it me?

[Scottyh]

A desparate first post!!!!

Four of my clients have sites with shared hosting with the host www.oneandone.co.uk. I am having immense problems getting anything registered on the engines, particularly Google despite decent to very good pagerank:

Vensol.net - nowhere on Google for London speed dating or less competitive terms despite page rank 5

Japaneseimports-south.co.uk - was riding high in Google but fell off a cliff in June. Still does well on MSN but now nowhere on Google.

shirleyeborn.co.uk - was top on Google for costume maker - fell away to nothing in July

frenchpropertymatters.co.uk - nowhere!!!!

My own site photoconnect.net was top for all sorts of photography searches but fell away in August - came back again in Sept after I changed host.

I have not been up to anything naughty. All site have reasonable pagerank. I've even removed links from my webdesign site because I thought I might be the problem!!!

My clients are getting desparate! Is this me - or oneandone - or what? Any ideas out there?

Thanks (I'm getting shouted at.....)

Scott