Solucionado
No pom do projeto, está escrito que tomcat-servlet-api será provided. No entanto, ao procurar as libs do Tomcat, eu só achei a servlet-api.jar. Como ele faz essa ligação? Minha pergunta completa está aqui:
https://stackoverflow.com/questions/48409826/how-tomcat-servlet-api-is-linked-to-servlet-api
Olá, Gabriel!
Vi que você recebeu uma resposta lá no StackOverflow.
Só complementando, o nome do JAR não é importante mas as classes (e também anotações e interfaces) fornecidas pelo JAR.
O Tomcat carrega o servlet-api.jar que terá os .class de classes como HttpServlet, HttpServletRequest e HttpServletResponse, entre outros, e os disponibiliza no Class-path. Essas classes serão carregadas conforme forem necessárias.
Para a compilação do projeto pelo Maven, você precisa de uma versão dessas classes. No caso, o artefato tomcat-servlet-api está como provided para indicar que ele não dever ser incluído no WAR. Não é uma dependência da aplicação, mas uma API fornecida pelo Servlet Container (ou servidor de aplicação).