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?
At least three faculty in my department (including our current head) have PhDs in electrical engineering, at least one has a PhD in mathematics, and at least one has a PhD in operations research. If a faculty candidate is actively publishing good research in computer science conferences and journals, which department gave them their PhD really doesn't matter. (And if they're not actively publishing good
research in computer science conferences and journals computer science research, they won't get hired, period.)
Most junior faculty candidates don't have significant teaching experience anyway, so that aspect really doesn't matter much either. Sometimes it can be a bit tricky to find courses for new faculty with non-standard backgrounds to teach, but if they're really doing CS research, something always fits.