My two cents...
I don't think ONLY having your link on the client's homepage will be better for
SEO,
PR, or anything having to do with the engines.
The purpose of
SEO is to bring in business (or at least money). I'd say a good number of my company's clients found us by that footer link or were referred to us by the client. Removing links from the interior pages might have some small effect on your rankings, but it would decrease traffic to your site.
What's my point? Fewer "less relevant" links
might help your ranking some tiny amount (emphasis on might), but
traffic to your site would probably decrease - which is bad for business.
Google/Yahoo/MSN might not care about those links anyways... they're probably all in the supplemental index. If some doomsday senario happened and the SERPs went down, how would you get traffic to your site?
The links in the footer of your clients' websites drive traffic - which is every bit as valuable as a top search ranking.