How should this situation best be handled? I didn't want to call a judge at that point because a) it was just my impression that's what he was doing and b) its just my word vs his word
Get a judge over there and talk to him discretely. The only way "it was just my impression" plays in is that you don't want to start yelling "my opponent's a cheater." Talk to the judge away from the table and tell him your concerns.
Yeah, there are two options, both involve DISCRETELY talking to the judge such that the judge can observe the player. One classic is to take a card from your deck, call a judge, and keep pointing at the card while telling the judge about the shuffling. But make it appear that you are asking a rules question about the card.
The other is to talk to a judge after the round and let the judge observe his behavior on later rounds. This might not work well if he has already scouted the next round opponent.