I solved the issue with mine. I was having 100% the same issue.
I tried using old MacBook Pro using Sierra, iMac with Catalina, MacBook Air Catalina and windows 10 (though VMware on iMac running Catalina).
I tried editing plist files etc reseting bluetooth/using debug mode etc etc. none will work.
here is how I worked my issue out.
I used an old MacBook (2008) and started installing older versions of Mac OS X until one was able to rename the device names permanently.
it appears once you install 10.7 (Mac OS Lion) it was able to rename the device permanently. to find the root cause I am investigating what changed from Mac OS 10.7 to 10.8 with the bluetooth stack.
but for now the solution to the issue is finding an older Mac using 10.7 and completing the re-naming process there. I hope this helps. If I can pin point the root cause of this I will try to work a fix.
it seems like Yudi Setiawan had success with 10.11
which I also agree Apple seems to have changed something between old versions and newer versions of OS X
I believe I found the root cause,
iOS and recent versions of Mac OS X restricts direct access to certain characteristics such as "device name"
this trick based on this should work on android device or a pc running windows natively.