Try wafflepool instead of just going back to middlecoin... Then watch your rejects drop to almost nothing, and profits increase along side.
How they manage to do that?
They probably just mine different coins with longer block times, which makes it less likely for you to submit a share for a block that is already solved. Terk seems to have calculated that these fast coins are worth mining even with sky-high rejects. Or he's wrong and Wafflepool is doing it right, I don't know.
On a related note, I would also appreciate an EU server. us.clevermining.com seems to be located in Seattle WA, which is simply too far away from me. US East Coast would be at least a little better.
--
@tyj8tim: Share difficulty has nothing to do with reject percentage. Or with overall profits, or with anything that matters.