Freezing cooked chicken from the deli?

Yes, you can freeze cooked chicken, no problem. As long as you follow safe food handling techniques, it is perfectly safe to defrost it for eating later.

Since it has already been cooked, you do not need to bring it back up to 165 deg F. Just get it to the temperature at which you want to eat it, and enjoy!

Do keep in mind that when you defrost your chicken, you should do it in the refrigerator rather that out at room temperature, where bacteria can begin to grow again. You can, of course, rapidly defrost it in a microwave, or just heat it from frozen, though this can give you uneven heating depending on how big the pieces are.

More info

As it pertains to bacteria, you can think of freezing as stopping time. So if your food is clean and safe when it goes into the freezer, it should be clean and safe when it comes out. The USDA has a guide to Freezing and Food Safety if you want more details.

Cooking chicken to 165 deg F mainly serves to kill salmonella bacteria. Once this has been done, your chicken is salmonella-free, hence you don't need to reheat to this temperature again.

Also see the very thorough post on food safety on Seasoned Advice with just about everything you need to know on the subject.