グレーな問題ですが、結論としては「できないことはない」ということになります。本件はちょうど法の区分の境目にある問題であり、それゆえ社内の紹介報奨制度は一般化していないという現状があるようです。問題となる法律は職業安定法の次の条文です。

第４０条（報酬の供与の禁止） 労働者の募集を行うものは、その被用者で当該労働者の募集に従事するもの又は募集受託者に対し、賃金、給料その他これらに準ずるものを支払う場合又は第３６条第２項の認可に係る報酬を与える場合を除き、報酬を与えてはならない。

私は以前この問題につき調査したことがあり、その管轄は埼玉県だったのですが、さいたま労働局需給調整事業課の回答によると、「紹介による報酬を払ったとしても、職安法４０条規定の「賃金、給料その他これらに準ずる」と認められれば問題無いので、就業規則に賃金の一種（「紹介手当」など名目は問わない）として明確に定めるのであれば良いでしょう」とのことでした。

具体的にいかなる条件を満たせば「賃金」に該当するか尋ねたところ、労基法がベースになるため同法の解釈は労基に聞いてくれとのことでさいたま労基に聞いたところ、「こちらは労基法のみ管轄であり、紹介制度についてはハローワークに聞くしかない」とのことでした。

そこで次にハローワークに電話したところ、ここは否定的な見解で、「いかなる名目であれ人を紹介してそれに対し対価を払うのであればそれは事業として許認可が必要ではないか」とのことでした。お役所らしい慎重な回答ですね。

以上踏まえますと、いずれにせよ取り締まり機関は労基である以上、人を紹介することも勤務時間内になされるのであればその報酬も「労働の対価」と言い得るので、実現させることは可能とは思います。

個人的には「成功報酬」とするため職業紹介の対価としての性格が強まるのであれば、現実には難しいかも知れませんが紹介する度に一定額を支払うという設定にすれば「労働の対価」と主張しやすいのでは、とも思われました。

なお、その相談者のところでは、内規を次のとおり改訂し紹介制度を導入したそうです。参考になさってください。

紹介による報酬を二分割で賞与に乗せて支給する（パートである場合は別途振込とする）形とし、最初の紹介時に前半を、被紹介者が１年後も在籍していた場合に後半分を支給。

賃金規程に「有資格者紹介制度」を追記し、有資格者の種類と支給額を決めたテーブルを明記（看護師なら１０万、介護福祉士なら２万等）。