When is deep learning overkill?
It's all about Return On Investment. If DL is "worth doing", it's not overkill.

If the cost of using DL (computer cycles, storage, training time) is acceptable, and the data available to train it is plentiful, and if the marginal advantage over alternative algorithms is valuable, then DL is a win.  

But, as you suggest, if your problem is amenable to alternate methods, especially if it offers a signal that matches up well with classic methods like regression or naive Bayes, or your problem requires explanation of why the decision boundary is where it is (e.g. decision trees), or if your data lacks the continuous gradients needed by DL (especially, CNNs), or your data varies over time which would require periodic retraining (especially, at unpredictable intervals), then DL probably is a mismatch for you.