I know this is an old thread, but I wanted to add some extra information that may be of use to someone somewhere down the line:
Here is a little thread I made, with a line-up of a LOT of CPU HSFs that started from s3 all the way to sA.
I made a quick edit and reuploaded that pic here (I also re-uploaded the pic that photobucket broke it's link to, for your convenience).
The attachment DSC00700b.jpg is no longer available
The 2 marked HSFs to the left are some of the easiest to find HSFs that are as beefy as can get without blocking anything on the board, as I was faced with this exact same problem years ago.
These are s370 Celeron/Coppermine HSFs and when looking from the top, these basically have the same dimensions as the CPU socket (a bit rectangular). The only thing I replaced were the stock Intel fan and often the mounting clip in exchange for one that is more convenient to use (I think people who actually worked with these particular stock Intel HSFs know what I mean).
As these HSFs do not exceed the dimensions of the CPU HSF (and because basically any CPU that fits ss7 won't actually need a sA-class cooling solution), these will never get blocked by components mounted on the motherboard 😀
It's worth having a look at, especially if one already has a substantial parts bin.