Definitely frustrating. There are a few websites that do this in some sites I'm trying to compete against and their websites are butt ugly. Where the keyword density for certain phrases reaching the point where the text isn't really readable for a user.

I'd just position it with your client that your users should be the first consideration, THEN the search engine. What's the point of a high ranking if your website's bouncing users from it left & right b/c it's so unreadable/unusable?

I say stick to your morals and it'll pay off in the end. Once Google finally figures out those sites have stuffed keywords they'll probably bring down the hammer on them and you'll be sitting pretty.