There are a few tip-offs that Verbal is Keyser Söze that become a Rewatch Bonus:
When they are released from the lineup and go out on the street, while Keaton is talking to Edie Finneran, the camera cuts to each of the others. In one shot Verbal is holding/smoking his cigarette between thumb and forefinger and palm facing up. This is an Eastern European trait commonly picked up by others in the region like, say, Turkey.
Before Kujan arrives, Verbal is shown glancing around the office, noticing details that he can turn into his impromptu story.
Before Verbal talks about Kobayashi, there's a shot of Verbal looking up at Kujan just as Kujan is taking a drink from his coffee mug, giving Verbal a clear view of the "Kobayashi" insignia on the bottom of the mug.
Verbal tells how Söze, confronted by a brutal rival gang, "showed those men of will what will really is" by shooting his own hostage-taken family and then the men themselves. Just a few scenes later we see him shoot the guy in the car that Keaton keeps threatening but never actually pulls the trigger.
Verbal's arrest is the the only one not shown despite the fact that it is Verbal who is telling the story. The reason is most likely because the details of his arrest wouldn't match the character he's presenting to Kujan.
Verbal smiles slightly when convincing Kujan that Keaton is in fact dead, stating that he knows it for a fact.
At one point, when Verbal mentions how someone like Keyser Söze won't stick his neck out if he is so close to being caught, he leans in closer to Kujan, sticking out his neck.
Peter Greene, the actor who played Redfoot, was uncredited because the character never existed.
The way things go down in the "jewel" heist is another point in favor of Verbal being Söze. First off, assuming that we can believe our resident Unreliable Narrator, Söze & Kobayshi set the robbery up in the first place so that when it went bad and Saul died, it would make the Suspects come to them and Saul's death would be blackmail material to use against the Suspects. That doesn't happen without the death of Saul Berg though. So when it looks like Keaton won't go through with his threats and kill Saul, who finally steps up to do it? Verbal. Why? Because he needs that death to lure the Suspects into a bigger trap.
As discussed on the main page, Keyser = Kaiser = King = Kint (ok, not perfect), Söze = 'easy with words' = verbal; using Batman logic, good with words = smooth talker = liar, making Keyser Söze the King of Lies. Kint and the Hungarian outright refer to him as "the Devil"; this also plays into the trope of Satan using wordplay to hide in plain sight.
A fairly overlooked detail is that whenever Keyser Söze is shown using his gun in flash backs, he's using his left hand. Fairly unimportant, until you realize that all of these flashbacks are being told by Verbal Kint, who turns out to be Keyser Söze in the end and just where is Verbal crippled? His left hand and foot. He's subtly trying to clear himself off the suspect list by making Söze out to be a lefty!