Just some random thoughts here about how I would proceed were I in your situation.
One thing you might try to do is place your ear close to the fan inlet port and start the laptop. If you can hear the fan spin up when the laptop starts, it should be in good enough condition to operate normally.
I take it you have already tried blowing out the fan and heatsink with canned/compressed air? If not, give that a go (and if using compressed air, be careful not to use too high a pressure on the air stream - about 20 psig is a good maximum, and even that may be too high in some cases. Short bursts from a few inches back (i.e., not at "point-blank" range) until you get a feel for things is better).
Before you go ordering parts, it might be wise to have a look-see and figure out whether the fan or the heatsink thermal coupling (paste/pad/whatever) is the problem. If you need to redo the paste, be aware that most laptop heatsinks are screwed down by screws that are numbered for the correct sequence of removal/reassembly. (That is, loosen and tighten these screws in numerical order.)
You may already know this, but if phase change material was used previously on the heatsink, the CPU die may become bonded to the sink. If this happens, attempting to force the sink loose may strip the CPU die of its upper cover or strip the entire CPU from the socket, both of which are undesirable events. Go carefully, and don't force anything.
I think, but can't remember for sure, that Sony used thermal transfer pads on their CPUs in the Vaio machines I have looked at in the past.
Do you have a pet? A dog or cat, perhaps, which may be shedding? I have seen instances where pet hair/dander got sucked into a machine a clogged the heatsink fins on the fan so badly that I had to disassemble the laptops in question to physically clean the fins with a toothbrush and a pair of tweezers (gently, though, or you'll bend the fins!)
You might look on YouTube for a teardown video before trying to disassemble your laptop (unless you're already familiar with how it comes apart and goes back together). A lot of the Sony Viao models are devilishly tricky to get apart. (I just did a quick search, and didn't find your exact model, but there are several that might be similar enough to work from...)
A check at Sony's support page for this model did not turn up any teardown instruction (no surprises there...).
This vendor's page gives what might be good general instructions, and is for your specific model, but I DON'T KNOW (found them on a Google search):http://www.cpu-fan-shop.com/sony-vaio-vgn-nr420d-cooling-fan.html
Good hunting on this one - keeping a laptop cool is almost always a challenge sooner or later.