前職の問い合わせは違法？

積極的に個人情報を開示することは問題がありますが、相手の問い合わせに対しYES or NOで答えることはありえますね・・・。

その辺は、実態に応じて阿吽の呼吸というのがあるのでしょうね。

個人情報保護法については疎いですが、労働基準法について記載があったので追加を。

労働基準法第22条では、労働者の請求に応じて事業主が退職証明書を遅滞なく労働者に交付しなければならず（第1項）、この証明書には労働者の希望しない事項を記載してはならず（第3項）、またあらかじめ第三者と謀り、労働者の就業を妨げることを目的として、労働者の国籍、信条、社会的身分若しくは労働組合運動に関する通信をし、又は第1項の証明書に秘密の記号を記入してはならない（第4項）とされています。

要は、「こいつは雇用するな」というブラックリストの作成の禁止なのですが、これについては一部の例外が（通達レベルですが）ありまして、特定の業法により、不適格者をその業種から排除するためにブラックリストを作成することや前職を確認することがあります（保険の外交員や警備員など）。この場合に作成されるブラックリストは必要最小限に限って労働基準法第22条第4項違反とはならないとされています（昭和24年9月12日基収第2716号、平成15年12月26日基発第1226002号）。

個人情報保護法ができて間もないころは全然お教えできません、でしたがはい、いいえくらいは最近答えるようにしています。

ただし辞職の理由はお教えできません、が多いようです。

対応が会社によりましてまちまちですので退職証明書を提出してもらうとか？

最近多い質問ですが、「個人情報保護法」は「個人の情報を保護するための法律」ではないです。

社員の在籍確認・退職者の在籍確認は、現在でも行われています。

もちろん目的外使用（勧誘等）は出来ませんし、自宅住所や電話番号・在籍時の勤務評価などは教えません。
ですが、
職歴確認で「○○さんが□□年△月～××年＊＊月まで在籍」程度の情報は提供します。
もちろん相手が会社の人事採用担当者であることを確認してから、になります。

＞応じることは違法ですよね？

何を持って違法と認識しているかわかりませんが、会社が違っても人事同士は仲が良いので、それなりに情報交換や交流はあります。
よほどへそ曲がりの会社で無い限りは、節度のある中で必要な業務は行います。

詳しいことはわかりませんが、下記のようなサイトの見解もあるようです。

個人情報は本人からの収集が原則で、本人の同意を得ないで前職の人事担当者が答えた場合は、問題が生じる可能性もあるようです。
「前職での職場での在籍確認」は、応募した労働者が前職の会社から交付を受けた「退職証明書」（労働基準法２２条）でも可能なようです。
http://www.jil.go.jp/kikaku-qa/jirei/19-Q02B1.html
http://www.jil.go.jp/kikaku-qa/jirei/19-Q01B1.html
http://www.kojin-jouhou.com/kojin3_06.htm
http://law.e-gov.go.jp/cgi-bin/idxselect.cgi?IDX …（職業安定法）
http://law.e-gov.go.jp/cgi-bin/idxselect.cgi?IDX …（労働基準法）
http://www.pref.fukushima.jp/roui/roushitoraburu …（退職証明書）

参考URL：http://www.kojin-jouhou.com/kojin3_06.htm