Don't feel bad for them. Their recruiting process failed, or their internal processes have failed, if they brought someone in and can't make them happy. They're a business. Mistakes happen. It won't put them out of business to lose you - especially if you give them a comfortable notice.
Some recruiters are really good. Most suck. Good recruiters will carefully match candidates to positions. Bad ones will throw whatever has a chance at the problem.
Find good recruiters and only use them. Ask for recommendations from friends if you don't know any. Recruiters are highly valuable because lots of jobs are never really published.
