Previously, the .devices() call passed the parameters in the wrong order. I checked the order in the interface and the daemon, and this was the only place it went wrong.
Now running kdeconnect-cli -l correctly lists all paired devices, even if unreachable.