What iron-clad reason did Dumbledore have for believing Snape was on his side? Maybe he was a good actor and a double agent. Was it just that he loved (or pretended to) Lily or he used legilimency?
Dumbledore didn't have "iron clad" reason. But he believed in the deep power of the ancient magic of love (with good reason - witness Harry being the ONLY ever survivor of Avada). And he knew the depth of Snape's feelings (after all, Snape came to him on his own to ask to protect Lily)
Dumbledore believed Snape because he saw how devastated he was after having betrayed Lily. At that moment, Snape swears to do anything and everything to get revenge at Voldemort, to defy him.
Maybe Dumbledore additionally used legilimency and saw Snapes true emotions. But there is no canon evidence for that.
Additionally, every time someone noticed someting suspicious about Snape and told Dumbledore, he already knew it because Snape told him himself or he had told Snape to do so (stopping Quirrel, the Unbreakable Vow, pretending to help Malfoy).
Adding something more to the answers.
The important thing to remember here is that everyone, including Snape, believed Voldy was dead.
The following excerpt from HP & the Deathly Hallows - chapter Prince's Tale. Conversation between Dumbledore & Snape in Snape's memories
Snape loved Lily. That is the Iron Clad truth. IIRC, Snape, after having mentioned the Prophecy to Voldy, pleaded him to let Lily live & only kill Harry & his father.
Snape was not the kind of person to follow Voldy out of fear. Snape was ambitious & looked up to Voldy. Voldy could have yanked Lily away & killed Harry & let her live. But he didnt care. Snape was obviously devastated. And Voldy was gone, so no double agent opportunities were yet presented to him.
When Dumbledore tells him that Voldy will return & the boy, who has Lily's eyes, would be in great danger, Snape has an opportunity to redeem himself, avenge his love & prove his love for Lily more to himself than anyone else