Tenure is a good one, but can be misleading. There are a few ways to make money in recruiting. Being really good at it and ethical is one way, but there are also people who are unethical and it hasn't caught up with them.

I would always suggest looking at their tenure. A new recruiter doesn't have the depth of client relationships to be all that helpful, but most new recruiters are 'sourcers' and not handling the client side (they are responsible for researching and bringing in candidates).