Se você pesquisar Allow Users to Edit Ranges na Review Tab na seção Changes , encontrará opções para permitir que os usuários alterem apenas determinados intervalos de células.
Assim que isso é ativado, eles não podem adicionar tabelas. Eu testei no Excel 2010. Não sei qual versão você tem, mas o mesmo recurso está disponível.
Existem até mesmo recursos para você definir permissões específicas para determinados usuários, se você escolher.