One thing that has been very helpful for me is reinforcing how valuable quick mental arithmetic can be. I recently taught about some great mental math shortcuts for squaring any reasonably sized number ending in 5, and using the difference of squares to quickly multiply any two numbers that are centered around an "easy" square (and now 5s are in that list as well as 10s). Upperclassmen in particular have tended to be fascinated by these "unlocks" - and I use them to illustrate how important the memorization of times tables is (up through 12s, at least, which was always good enough for me). At the Calculus level specifically, it might be worthwhile to assign some basic derivatives with higher exponents, and make them do it in class without the use of a calculator. Even though we normally only run into variables with relatively low exponents (especially at the HS level), this can be a good way to sneak in some times tables drilling without deviating from your curriculum.
Since my students respect my expertise on the subject, I try to communicate to them the mental techniques I use when doing a problem in my head. Every teacher has their own stable of tricks; have you shared yours with your students? They seem to take notice of that, and when I tell them they shouldn't be using a calculator for a simple problem, they usually agree with me. Once they feel that way, the next step is teaching them how we made it easy for ourselves - so, you'll have to remember the methods you used that worked in your own mind.
Another technique that has worked for me, if you can spend some time on it in class, is to hammer the memorization in as many different ways as you can: Flashcards, timed drilled written problems, any sort of game involving rapid mental calculation, etc. I know it's not technically your job in a calculus course to review elementary ideas, but a single day spent on this can be fun for students if done right, and will end up benefiting them much more than another day of over-relying on the calculator. I use the analogy with my students that the calculator is like a crutch, and you won't build your mind up to be strong enough if you lean too heavily on it.