Update: Problem solved. Uninstalling Bluetooth drivers and downloading 7265 AC drivers from Intel helped. For whatever reason, the Bluetooth drivers listed for NU5i5RYH on Intel's website don't work, neither do those supplied by the Intel Driver Update Utility. Searching on Intel's Download site for drivers for 7265 AC (Win 7 64-bit) solved the problem for me.
I celebrated too soon. Now I have no Bluetooth whatsoever - no Bluetooth devices in device manager, no Bluetooth icon, no Bluetooth in Control Panel. In other words as if my computer didn't have a Bluetooth device at all.
I am not aware of doing anything in particular when Bluetooth stopped working. I've installed a few non-related programs (a video editor, a couple of games, maybe some Windows updates) in the last week, but I can't recall Bluetooth disappearing after any single change. It just wasn't there one morning.
1. Checked BIOS - Bluetooth is enabled. Tried disabling, rebooting, enabling, rebooting, nada.
2. Uninstalled all Bluetooth drivers (the Intel Bluetooth driver installer lets me choose "remove").
3. Re-installed the same drivers I used before. They install just fine.
4. Checked Bluetooth services in Service Manager - all three running and auto-starting.
5. Still no Bluetooth whatsoever. Have tried uninstalling and re-installing my Bluetooth drivers many times, also using different Intel Bluetooth drivers, uninstalling and re-installing all network (wifi etc.) drivers.
6. No Bluetooth. At all.
Running Windows 7 Ultimate 64-bit. At my wits' end.
Works now. Tried everything I could software wise ... I finally opened the NUC physically, pressed gently on the integrated wifi-card and antenna connectors, screwed the lid back on and turned the NUC on and ... Bluetooth works. Just like that. I couldn't detect any movement whatsoever when pressing the (integrated!) wifi card and antenna connectors, everything felt solid, but I can only assume that something must have been loose. Wifi's been working flawlessly all the time...
I really hope this was it. If not, screw Intel.