Yeah that was Obilic Belgrade, who won the Serbian League and came second in 1999 - every other year it Red Star and Partizan in the top two except in 2008 when Vojvodina came second and Red Star 3rd.
I think Zenit is a bit different to Obilic and Depor. Firstly they have historically, even in Soviet times, always been a big domestic club. There were bigger and historically better clubs in the USSR (Dyanmo Kiev, Spartak Moscow, Torpedo Moscow) and Zenit only won the Soviet League once, but nonetheless they would usually finish in the top half and would still be considered a fairly big team given the size of the Soviet league.
Secondly they are the only team of note in St. Petersburg, a city of nearly 5 million people. There is another team called Petrotrest (used to be called Dynamo) who play in the third level of Russian football, and there is another new team called "Pitar" again playing at this level, but both of these clubs are not very strong and have never had a massive following - it would be like say Barnet in the context of London or a team weaker than Unterhaching in the context of Munich football. What is in effect the only team in 4th/5th biggest city in Europe (or the 2nd biggest city in a country with over 140m people) always has the potential to be a big club and indeed in the past (save a disasterous period in the late 1980s early 1990s when the whole of the USSR / Russia was in crisis) has been a fairly big club). A lot of famous current footballers come from St. Petersburg - as well as Arshavin, Malafeev, Denisov etc, there is also Yarmolenko. Being the only sizable club in the city does give them an advantage, at least in terms of fan base, that the Moscow teams don't have. For instance Moscovites could choose from Spartak, CSKA, Dinamo, Lokomotiv (and in olden days Torpedo) whereas someone from St Petersburg who likes football is usually going to be a Zenit fan.