Justilien - 1:05 pm on Oct 18, 2006 (gmt 0)

Create a great resource for their site. Find something that will solve a user's problem. Then promote that resource for people to link to.

Quick Example:
They are a staffing agency. They could offer HR (Human Resource) advice to small and medium size businesses. This could be in the form of a blog or a FAQ section. Every business is in constant need of HR advice from motivating, hiring, firing, etc.

Your client gets a quality resource that can be used to attract links. The site gets great additional content. Plus, they may even land clients from the resource.