@AAQ:
The Rabbonim who ruled in the case in question were Rav Herzog, Rav Ben-Zion Uziel and Rav Shaul Yisraeli; the city in question was Haifa. It should be noted that Rav Herzog changed his stance from using bikes/horses to using cars. My understanding is that the background is more or less what you said it was.
Halachik sources: (1) Heichal Yitzhak (OC 32): Rabbi Herzog’s original thoughts on police work. (2) Amud HaYemini (Siman 17): Rabbi Shaul Yisraeli’s expansive defense of police activity on Shabbat. (3) Techumin (Vol 7): Often contains retrospectives on these early state-building psaks.
The actual pesak seems to be maintaining public order (which includes stopping stealing cars) falling under the category of pikuach nefesh – the State cannot function if it totally shuts down for 25 hours each week. Use of a bike would not help, so cars may be used, but some shinui needs to take place when starting the car.