I don't see mention of Oblivion Stutter Remover (OSR). That utility can go far to reduce certain types of stutter. You'll want to experiment with its heap-replacement feature. No one mode seems to be ideal for every individual install. Checking out its thread in the Mods forum should give you an idea of how to install and configure it. Requires OBSE of course, but if you don't already use OBSE that too is a super easy install.
I asked about SSD here a while back. Replies weren't enthusiastic enough for me to consider it a must-have. Things might have changed.
To an extent what you suffer "is" normal. Oblivion's game-engine is old. It does not take full advantage of modern multi-core CPUs and the latest high-end GPUs (or multiple GPUs). Still, properly installed and configured utilities can go a long way to made Oblivion smooth-running and stable. The in-game Options menu sliders can help reduce stutters/lag too, so long as you don't mind trading image quality and/or eye-candy for better performance. 40FPS should not worry you. Oblivion runs smoothly at that rate. Heck, OSR caps FPS at 30 for me. (This can be overridden if you prefer a higher cap.) I normally don't notice "lag" until the very low 20s, and it's not bad until I hit the teens...which is blissfully rare. Stutters are another matter, but I can get those at any FPS.
That 5850 should run the game fine. I thought long and hard about getting one when I assembled my current computer last year. Ended up going for a GTX470 instead.
Aye, Oblivion.exe can be flagged as LAA (large-address aware). Yes, it "can" help, though don't expect miracles, especially with "only" 4gb ram. At the very least it should do no harm so long as you use a 64-bit variant of Windows. (Don't bother with it if yours is 32-bit.)