3 hours ago we dismounted both APs from the ceiling and patched them up directly to the Switch. So far they are both running fine, however there are not so many people in the office today, so the APs are not really busy.
It possible that the cable going to the ceiling has a wonky connector crimped on, creating additional resistance and adding few Wats in loss to the total sum for which the AP didn't account for when negotiating power from the switch. It's a stretch, but possible..
I will monitor the situation and post an update during the week.