Wow, there's a lot of good answers here.
Trying to synthesize a few of them....
The deal - company to recruiter
The money a recruiter makes is not the same payoff that you would get by finding the job without the recruiter. It's the money the company might otherwise be paying their HR department to find people without the use of a recruiter or possibly the money the company may pay other employees for referrals.
The deal - you to recruiter
Whenever you work through a third party, you need to get a sense of that party's goals and business models. Some recruiters will just want to place as many people as possible to get as many fees as possible. Others are very sensitive to their reputation and will only set up cases they believe are a win/win.
When a recruiter is helping to guide you towards jobs that work for you and the company, you have a good chance of success. When the recruiter is pushing you to broaden your resume with skills you don't possess, or when you get an inkling they are selling you as something you are not - be wary. If the recruiter is just looking to fill a quota, they can easily waste your time and the company's time.
Realize that different companies have different models for how they do recruiting and hiring decisions. It varies widely from industry to industry and also company to company. Some will NOT work with recruiters, some will work with recruiters but only within some tightly defined limits (for example a job that must be open +3 months before it is farmed out to recruiters), some will ALWAYS work with recruiters.
Saying "absolutely no" will reduce the company pool, eliminating those companies who work exclusively with recruiters.