It’s taken almost a year, but I’ve finally got Vegas Pro 12 working properly with mp3s and other missing formats.
I ended up uninstalling Vegas Pro 12 and plugins, and then downloading the latest installer (Build 670) and trying it again. Apparently the problem was related to file verification. When you register Vegas, sometimes unregistered files would get skipped and in this case I assume it was the lame codec. This is my theory anyway.
Hope this helps people out.