Looks like your board does have the holes, the 8K3A+ is listed on Alpha's 8045 compatability page.  Still a fan of bolt ons, 8045 is working out quite nicely for me and has outlived 3 cpu upgrades.
With 2 pristine lugs though I wouldn't have any worries about going with a 3 hole clip.  Can pick up a SK6 over at 
SVC for like 13 bucks.
Edit - see you asked about bolt ons.
Alpha 8045 and it's cousin the 8942
Thermalright SLK-800 and 900
And the Switchtech 462
There are 5 to get you started.  Some of the newer ones are also compatabile with the P4 retaining mechanism if that's something that might appeal to you for the future.  The bolt ons tend to be pricier, also tend to be higher end sinks.  SLK-900 is a beast.  SK6 is still a nice choice though, mostly depends on your CPU/cooling needs and what changes in approach you want to take with this incident...er, opportunity...as far as noise and such.