PC shutting down after 30 minutes, even when on BIOS screen

A few of suggestions:

1. Try booting in safe mode and see if it still happens. That might isolate a malware or driver issue.
2. It could still be a power supply issue. If the amount of required power is right on the edge of what your supply can deliver, it might be that when you swapped in another [assuming it has the same power rating], it suffered the same issue. Try a power supply with a higher power rating.
3. I once had a case here the video card was causing the computer to only make it part way through POST before causing a shutdown. Now, that was different, in that it happened after a few seconds and not 10s of minutes like in your case ['cuz a video failure was detected by POST], but who knows. If you're using a video card and your mainboard has it's own video processor, then try removing the video card and plug a monitor into the mainboard video port, and see if the problem goes away.
4. Capacitors are notorious for this kind of failure. For instance: the bond between one of the leads and the capacitive component comes loose but still makes contact, until it gets hot, where dissimilar expansion causes the lead to fully separate from the component. This can occur in other types of component, as well, but in all cases can be difficult to troubleshoot without the proper equipment [and even with]. A can of freeze spray can be used to locate such a thing [but only if you can reach the offending component] -- use a "divide-and-conquer" approach.

5. Some ICs have internal thermal shutdown -- especially regulator ICs. Mainboards often have linear regulators and if one of them is heating up, it may be shutting down a critical function. Try scanning the board with a non-contact temperature sensor [or even better a thermal imaging camera]. At around 20 to 25 minutes after power-up, look for devices that are hotter than surrounding devices, then hit them with freeze spray. If the computer doesn't shutdown at 30 minutes, then you have likely found your culprit. Then it's just a matter of replacing the part. BUT, consider that the part [especially if it's a regulator] might be getting hot because something else is drawing excessive current. The possibilities:

   A. It might be normal for the part to get hot, and something internal to the part might have failed, causing it to shutdown at a lower temperature than it's specified to do so. In which case replacing the part would be the best course, or consider option C.

   B. Track down the cause of the excessive current. This will, probably require a schematic, and can be very difficult.

   C. Put a heat sink on the part. This is a "band-aid" approach [like using chewing gum to repair the throttle linkage on a race car], but what the heck, if it keeps you going, then why not! You can get heat sinks with peel-and-stick insulator pads [search on "heat sink" at Amazon, for instance] -- also there are many for XBox and Raspberry Pi GPU]. Look for one with the best fit for the part.

6. This is a shot in the dark, but I had a similar problem, once, and I traced it to the backup battery.

Problem solved: it was the motherboard.

I obtained a replacement under warranty and switched it out. The original motherboard will be going back to the manufacturer, so if I find out what the issue with it is I will post an update here.