Maybe this is new in US, but paying recruiting agencies is nothing out of the ordinary in many European countries, at least if you actually want to have a recruiter that cares about where you land as position.