That is what I thought, which is also true in Spanish. Is it really even correct or common in Brazilian Portuguese to omit "que" in this case?

"Ele responde que não" is accepted as of June 2017.

"resposta" is the noun "answer". "responder" is the verb meaning "to answer". "responde" is its third-person singular present tense conjugation.