I would like to know how willing would staff in CS department of reputed universities would be to hire doctorates from relevant non-CS departments, for example, say, management science or operations research students. I see a dilemma for the recruiters here: research-wise the new member may be probably better-equipped to span a newer vista of problems that are currently not tackled in the department, but academically, the faculty may not be trained to teach usual CS courses at undergrad level.
A few specific cases, in either case you can assume the applicant is interested in CS research, but does not have publications in top CS journals:
The applicant is a CS-graduate and a PhD in MS but has no CS teaching experience.
The applicant is NOT a CS-graduate but a PhD in MS who has worked on CS-related problems for his doctorate. Will he be excused for not teaching undergrad? Or will he have the liberty to formulate interdisciplinary courses himself and teach them?