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.