I've dealt with Footsteps on a professional level and they've seemed up front and straight; note that I've not had anything to do with placements with them but they've contributed some stuff to our site.

There are about 14 recruiters I know of in China so I'd personally write to every single one with some awkward questions and see what comes back; you'll have a good idea of who actually reads your email and bothers to reply properly and who just sends back a stock reply which implies they don't really care.

Henry