This is covered in some detail in the movie's wiki. The toss up wasn't between Van Cleef and Volonté for Angel Eyes, the Bad. It was actually between Van Cleef and Charles Bronson (who he later cast in Once Upon a Time in the West):
Originally, Leone wanted Charles Bronson to play Angel Eyes but he was already committed to playing in The Dirty Dozen (1967). Leone thought about working with Lee Van Cleef again: "I said to myself that Van Cleef had first played a romantic character in For a Few Dollars More. The idea of getting him to play a character who was the opposite of that began to appeal to me."
On the other hand, Volonté was considered for the part of Tuco, the Ugly, but was deemed not comical enough:
The director originally considered Gian Maria Volonté for the role of Tuco, but felt that the role required someone with "natural comic talent". In the end, Leone chose Eli Wallach based on his role in How the West Was Won (1962), in particular, his performance in "The Railroads" scene. In LA, Leone met Wallach, who was skeptical about playing this type of character again, but after Leone screened the opening credit sequence from For a Few Dollars More, Wallach said: "When do you want me?" The two men got along famously, sharing the same bizarre sense of humor. Leone allowed Wallach to make changes to his character in terms of his outfit and recurring gestures. Both Eastwood and Van Cleef realized that the character of Tuco was close to Leone's heart, and director and Wallach became good friends. They communicated in French, which Wallach spoke badly and Leone spoke well. Van Cleef observed, "Tuco is the only one of the trio the audience gets to know all about. We meet his brother and find out where he came from and why he became a bandit. But Clint's character and Angel's remain mysteries."
The wiki sources this information from the book, Sergio Leone: Something To Do With Death by Christopher Frayling.
