This is common issue and usually indicates either a mesh problem or a latency issue. The pairing fails to complete in a timely fashion or some information may be lost in the mesh while pairing which is what causes the device to eventually show up with the wrong device handler, complete information and renders it inoperable.
In addition to what you’re doing, you may want to try these steps: [RELEASE] Universal Enhanced Z-Wave Lock Device Handler for Schlage, Yale, Kwikset, IDLock, Popp, Danalock, August Pro, Keywe, Philia, Samsung - #1464 by RBoy
It also helps to search your mesh for any ghost devices and get rid of them: FAQ: How to remove ghost devices from your z-wave and zigbee networks
If you have a newer Z-Wave Plus module like the BE469ZP model, you should use S2 pairing (using the Generic Z-Wave device option) from the ST mobile app.