I think the reason for denial is the same for everyone "marriage not genuine". Our red flags were a previous marriage to a Canadian (more than 10 years ago), no process was initiated and that my husband did not know much about me which is nonsense as we know each other for almost 10 years).
About the proof, we have sent things dating back to the date of denial which included phone call records, emails, letters, photographs, supporting letters from both his and my parents and some supporting letters of mutual friends back in his country, money I have sent to his phone, so we can communicate. I also wrote a letter about our relationship starting all the way at the day we met for the first time, my husband wrote the same kind of letter. Also my trips as well as the passport pages with all the stamps. The major thing is constant communication, on a daily basis, they want to see that! Hope this helps!