UWP BluetoothLEDevice "Element not found. (Exception from HRESULT: 0x80070490)"

I need a BluetoothLEDevice to connect via GATT. Here is the most simplistic code in a plain new Universal App I could come up with:

protected async override void OnNavigatedTo(NavigationEventArgs e)
{
    base.OnNavigatedTo(e);

    var devices = await DeviceInformation.FindAllAsync(BluetoothLEDevice.GetDeviceSelector());
    if (devices.Count <= 0) return;
    this.bluetoothDevice = await BluetoothLEDevice.FromIdAsync(devices[0].Id);
}

The method BluetoothLEDevice.FromIdAsync always throws the exception: "Element not found. (Exception from HRESULT: 0x80070490)"

I'm courious if it may have to do with the device capabilities. My device capabilities in appmanifest look like this:

<Capabilities>
  <Capability Name="internetClient" />
    <DeviceCapability Name="bluetooth.genericAttributeProfile">
    <Device Id="any">
      <Function Type="name:genericAttribute"/>
    </Device>
  </DeviceCapability>
</Capabilities>

I also tried those methods to obtain the device:

var devices = await DeviceInformation.FindAllAsync(GattDeviceService.GetDeviceSelectorFromUuid(new Guid("XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX")));

var devices = await DeviceInformation.FindAllAsync(GattDeviceService.GetDeviceSelectorFromUuid(GattServiceUuids.GenericAccess));

Every method returns a list with both of the 2 paired BluetoothLE devices. The first method (BluetoothLEDevice.GetDeviceSelector()) however returns devices with empty name fields whereas they have the right name with the other 2 methods.

I couldn't find any example with the same issue anywhere and nobody even seems to care about exception handling when using "BluetoothLEDevice.FromIdAsync".