It seems that Holmes's assessment of Milverton as "the worst man in London" was due less to long experience of the man than to the extreme revulsion he felt about him. It didn't take an exceptionally long study of Milverton and his methods for Holmes to get the gist of the man, and to realise that he was essentially worse, in his effects on others, than nearly any other criminal.
Here's how Holmes first describes the master blackmailer:
Do you feel a creeping, shrinking sensation, Watson, when you stand before the serpents in the Zoo, and see the slithery, gliding, venomous creatures, with their deadly eyes and wicked, flattened faces? Well, that's how Milverton impresses me. I've had to do with fifty murderers in my career, but the worst of them never gave me the repulsion which I have for this fellow.
After describing to Watson in detail the way Milverton works and the people he has ruined, Holmes concludes:
I have said that he is the worst man in London, and I would ask you how could one compare the ruffian, who in hot blood bludgeons his mate, with this man, who methodically and at his leisure tortures the soul and wrings the nerves in order to add to his already swollen money-bags?
Watson notes that Holmes is very worked up, much more than usual:
I had seldom heard my friend speak with such intensity of feeling.
Something about Milverton and the nature of his crimes touches Holmes in a way that few criminals can. Note that Holmes doesn't say he's the most dangerous man in London (a title which, if memory serves, he reserved for Moriarty, with the second most dangerous being Colonel Sebastian Moran), but the worst. This is a highly subjective evaluation, and likely based more on Holmes's personal revulsion than anything else. Allowing himself to make judgements based on his feelings is somewhat out of character, true, but we see from Watson's line above, not to mention his engagement and burglary later on, that he does act somewhat out of character when it comes to Milverton.
To summarise: Holmes's evalutation of Milverton is (rather uncharacteristically) based more on his immediate feeling of disgust than a long rivalry with the man.
There are also some hints in the timeline of the story which suggest that his acquaintance with Milverton began not long before the story begins. After the encounter with Milverton at the beginning, Holmes puts on one of his disguises and spends "some days" out in Hampstead investigating Milverton. He needs this time to establish a contact in Milverton's household and to get to know the building well enough to successfully execute the burglary 13 days after the start of the story. If he'd already been investigating Milverton for a long time, it seems likely that he might have at least some of these resources already in place, rather than doing the entire thing in 13 days.
Finally, I noticed this quote which I think really clinches the issue:
Between ourselves, Watson, it's a sporting duel between this fellow Milverton and me. He had, as you saw, the best of the first exchanges, but my self-respect and my reputation are concerned to fight it to a finish.
Holmes specifically says that Watson "saw [...] the first exchanges", and Watson's first encounter with Milverton was within this story - at the beginning of the story, Watson hadn't even heard of him. If Holmes and Milverton had encountered each other before, then that meeting wouldn't have been "the first exchanges" between the pair, and Holmes wouldn't have made that statement.
