There are a few tip-offs that Verbal is Keyser Soze:
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 mentions (not an exact quote) that part of what makes Keyser so dangerous is having the will to do what the other guy cant, then 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 starts to recount incidents where he wasn't there. His arrest is the the only one not shown despite the fact that it is Verbal who is telling the story. The reason is of course because he is Soze and wasn't arrested.
His response to hearing about Keyser Soze was "Oh, Fuck" as he had presumably originally planned to never have Keyser Soze become known.
Verbal smiles slightly when convincing Kujan that Keaton is in fact dead, stating that he knows it for a fact.
Peter Greene, the actor who played Redfoot was uncredited because the character never existed.
Dean Keaton makes a big deal about engaging two groups of heavily-armed and hyper-alert men, totaling over 20 people, in close quarters with just the four of them. He says the job is a suicide mission that can not be done. Keaton should know what he's talking about, being the most experienced of the group except Kint/Soze. With that in mind, the final raid seems too easy, and none of them get so much as a scratch before they were backstabbed by Soze. It seems a bit odd that an ex-criminal with as much experience as Keaton would be so wrong in his estimation until one remembers that Keaton thought they would be raiding a ship carrying cocaine. If the ship had been carrying 91 million dollars worth of cocaine, the guards would know the cargo. They would be very alert, ready for combat. In this circumstance, the raid probably would have been a suicide mission. But in reality there was no cocaine on the ship. Besides a handful of high-ups, most of the guards didn't know about the nature of the transaction any more than exchanging lots of money for one person. They probably were in the mindset of routine bodyguard job instead of being hyper-alert for a dangerous transaction, making them very unready for the attack. All of this was anticipated by Kint/Soze so he was sure he could get aboard to take out the rat.
The way things go down in the "jewel" heist is another point in favor of Verbal being Soze. First off, assuming that we can believe our resident Unreliable Narrator, Soze & 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.
It's easier to realize that Verbal is lying when he starts to recount incidents where he wasn't there.
Interestingly as part of the above, 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 of course because he is Soze and wasn't arrested.
Another hint: when Kint explains to Kujan who Söze is, he talks with the confidence of someone who has feared the mythical mobster his whole life, yet in his story of meeting Kobayashi for the first time says "Who's Keyser Söze?" pointing that either he lied to his cronies to muddy the tracks or fabricated the story wholesale for Kujan's benefit.