Bom, dia, Anália
Embora esta questão seja pertinente à área "Legislação Estadual e Municipal", adiante deixo minha opinião:
1) Visto que a SEFAZ está cobrando e a empresa não encontra a guia supostamente paga, isto é à primeira vista um indício de que realmente esta guia não foi paga.
2) Se houver a certeza absoluta de que esta guia está quitada, uma boa solução seria comprovar este pagamente:
2.a) Se foi pago pela internet, apresentar o extrato bancário
2.b) Se foi pago em banco, procurar a agência e solicitar cópia do movimento do caixa que recebeu o tributo, ou então, a guia autenticada que fica na agência (as guias de impostos são feitas no mínimo em duas vias, sendo uma para o contribuinte e outra fica na agÊncia para controles internos); para tanto é necessário informar em qual dia foi feito o pagamento.
Boa sorte.
PS: Mesmo assim, presumo que esta questão seria melhor respondida na sala que acima indiquei