Yes, I've done all of what you said. Well, stutter is maybe too strong a word, maybe I should have used frame skipping. Are you sure you never get that? When shooting, driving around corners, being on foot/in car in crowded areas?
I know exactly what you mean. The game is still responsive and most likely running at around 60fps, but yes, the way you describe it as like frame-skipping ... that's how I'd describe it too. I have a really weird solution. I'm too lazy to bother turning programs off manually whilst running a game, so sometimes I use this: https://www.razerzone.com/cortex
Strangely, when playing the game through Razor Cortex almost all stuttering is gone. There may be the odd micro-stutter every half-an-hour or so, but otherwise it's fine.
I'd figured that because you can have Razor switch off your background processes and whatnot to improve gaming performance, and seeing as I set Razor to turn off most non-essential stuff, then surely one or more of these processes must have been causing a conflict when they were allowed to run when I wasn't using Razor. I then launched Razor and re-enabled all processes, expecting to recreate the stuttering. Strangely, there was no stuttering. In other words, I haven't got a clue, but Razor seems to get rid of the judders in Mafia for whatever reason.
*edit* reading that back. I sound like a Razor Cortex salesman. I'm not! It's free anyway :D
Normally, I'm not bothered about software like that as it's a bit gimmicky, but it honestly does work with Mafia for me.
I'm not getting any stutter while just driving and walking around, only micro stutter while going on a rampage with the cops/other gangsters and then escaping in a car and drive-by shooting. Do you not get that?