I can stop somewhere after work to grab some new paste, but even without thermal paste... I'm only running the BIOS - nothing else is started up yet. It seems fishy that this is heating up so fast. Could it be something else?
It's not fishy. The CPU is running full blast in BIOS since none of the power saving features are active yet. You'll actually use less power sitting on your desktop since the CPU will throttle down via speedstep if enabled.
Also, I wouldn't trust your reported BIOS temperatures. I know on my board BIOS will usually report mid 40's, but once I'm in windows every other program reports high 20'C to low 30'C range.