Windu provavelmente assumiu que Maul era um Sith porque sabia que ele não era outra coisa. Tenho certeza de que os Jedi vigiavam todos os seus membros que deixam a Ordem, e eles sabiam que nenhum deles tinha desonestos (ou talvez seja tão simples quanto nenhum deles era Zabraks).
Provavelmente foi uma combinação de fatores que fez com que Windu pensasse que Maul era um Sith, em oposição a um membro de uma das várias outras organizações que usam a Força na galáxia.
Primeiro de tudo, Maul foi capaz de bater Qui-Gon em um duelo de sabres de luz. Obviamente, Jedi são mortos de vez em quando, mas não em um duelo de sabres de luz assim. Além disso, Qui-Gon era um Jedi muito poderoso, ao nível de um membro do Conselho. (A única razão pela qual ele não estava no Conselho eram seus métodos pouco ortodoxos.) Além dos Jedi, o único grupo que usava a Força que treinava no uso de sabres de luz era Sith ou afiliados Sith.
O sabre de luz vermelho também teria sido um fator. Até onde eu sei, não havia nenhum usuário de sabre de luz vermelha que não fosse Sith / Dark Jedi naquela época. Obviamente, nenhum Jedi faria um sabre de luz vermelho, e assim como só os Sith eram os únicos capazes de empunhar um sabre de luz, os Sith também eram os únicos capazes de construir um sabre de luz.
Além disso, a existência de Sith explicaria a crescente escuridão na Força que os Jedi já estavam sentindo. Os Jedi puderam observar que nenhuma das outras organizações da Força estava aumentando em poder.
É importante lembrar que teria havido pouca distinção entre "Sith" e "Usuário do lado negro" na mente de Mace Windu. Até agora, na história dos Sith, mais ou menos todos os usuários do lado negro eram Sith. Foi somente após o estabelecimento da Regra de Dois que a definição de Sith tornou-se mais discriminatória.
Veja também: Quando & Como Yoda veio a saber sobre regra de dois?