会社の許可なく残業をしている従業員から残業代を請求されています。残業代を支払わなければならないのでしょうか？

「会社の許可なく」という点ですが、就業規則等で残業が許可制とされていることが前提となります。
許可制の場合、残業代を支払わなくても良いのは次の２つの場合です。

　①　・会社が気付かない形で残業をしていたこと。
　　　・残業が必要なほどの業務を与えていないこと。

　②　・残業が必要なほどの業務を与えていないこと。
　　　・会社が残業に気付いた都度、(元)従業員に対して残業を終えるよう注意したか、事後的に気付いたなら今後残業禁止を守るよう注意した。

①のケースはあまり想定できませんが、タイムカードを定時で押して実は残業してた、こっそり資料を自宅に持ち帰って仕事をした、などが一応考えられます。これらの場合は会社が残業に気付きようがありません。
また、残業の許可制は原則残業禁止ですから残業が必要なほどの業務を与えることは矛盾します。

②のケースが多いです。残業の許可制は原則残業禁止ですから残業に気付いていて注意しなければそれを実質的に残業を許可したことと同じになります。

これまでの残業については以上の①と②で判断し、以後はもし無許可の残業をしたなら懲戒処分もあり得ることを警告するというのも一つです。
くれぐれも残業に気付いたら根気強く注意することを止めないようにしてください。そして、過大な業務を与えないようにしてください。
　

　
この回答をご覧になっても解決に至らない場合には、お気軽にお問い合わせください。