I don't trust this. Unless they are an employment agency, I don't see why they should charge a fee. And the reputable employment agencies don't charge you fees up front, they take it out of your first salary. I'd be wary.
Does anyone here work with this company?