If you are happy the battery is actually holding 12.5v, then I guess the next place to try is both the engine grounds and the main engine fuse/relay box. Make sure any bolts/nuts are tight.
Is the starter clicking at all?
Is the starter clicking at all?