Thanks for all the quick input folks. Boots are just a "tester" pair to see if my wife likes hardbooting or not.
Getting the old heels off was hellish. I ended up taking some pliers and a hammer and just prying the plastic heels off (leaving screws intact), then I took a hammer to the protruding screws and hammered them through the heel so the insets popped out inside the boot. After they all popped through, I just grabbed them and held them still with needle-nosed pliers.
I'll order 98965A210 Metric Zinc-Plated Steel Tee Nut, M5 Internal thread, 8mm Barrel Height, 4 prong and let you know how it goes.
Oh, but wait - where do I order them from!?