こんにちは。
私もそれほど詳しくはないのでリンクばかりで申し訳ないのですが、
すでに書かれている通り、職歴照会が違法なのではなく「本人の同意なしに」照会した場合は個人情報保護法に反します。
個人情報取扱事業者は「体系化されたデーターを５０００件以上持つ会社」と設定されているで御社がそれにあたるのかは確認してみてください。

こちらのＨＰで詳しく解説されてます。
http://www.nec-nexs.com/privacy/about/company.html
違反時の罰則についてはこちら
http://www.nec-nexs.com/privacy/explanation/penalty.html

ただし、雇用関係についてはさらに個人情報の取扱いがデリケートなので厚労省から平成１７年に
「雇用管理に関する個人情報の適正な取り扱いを確保するために事業者が講ずべき措置に関する指針」
というのが出ています。
こちらが解説ページ
http://www.mhlw.go.jp/bunya/roudouseisaku/privacy/050308-1.html

本人同意については第３条２項に出ています。
そして第４条には取扱事業者以外が出ています。
事業者以外も努力義務として定義されていますので、刑事罰はありませんが民事訴訟になれば対応が必要となるかと思います。

情報を提供した相手会社も同様の扱いか、取扱事業者の場合は刑事罰もありとなります。
民事訴訟するかどうかは本人次第だと思います。

もしまだ本人と話していないなら、現在の仕事の状況がこちらが望んでいたものに達していないこと、
前職での実務内容はどんなことをしていたのか再度詳しく話を聞くところから始めてはいかがでしょうか？
（故意かどうかは文面からは判断できませんが、本人が実務と思っていたことがこちらの実務とずれてるなんてこともあったりもしますから）