Well, I installed the custom library and uncommented my test code I used a while back. It seems that it still works fine in the sense that I can enable vibrations and sounds and they still work on my phone, and of course with those disabled, I get no vibration or sound on my phone. So far so good.
So the big test will be whether or not this fixes the issue on the small handful of affected phones. I was working on a minor update last night (slow night at work!) and stumbled on a bigger issue that bothers me so I will probably release an update today. I don't have time to wait on the one guy who tested the notifications for me so I am going to just release it and see how people react in the comments.

If it seems to be fixed, I'll add it to my release notes, otherwise nobody will have to know I even tried.
On the issue itself.....
Yes, the other app is free and I suppose I could reverse engineer it. However, I assume he just initializes the object the way he wants it from the start (no vib, no sound). I think it is conceivable that for whatever reason, on some phones perhaps it just goes with the original initialization options? I have no idea. I don't even know how this works. Does your library control the B4A object (which in turn controls the true Android object) or does your library control the true Android object directly?
That probably doesn't even make any sense, and if not, that would be because I don't know what the hell I'm talking about.
Hopefully this will do the trick, and if so, I will most definitely update this thread either way. I think that if it does happen to fix it, then perhaps an update to B4A would be in order, but we'll see what happens first.
I appreciate your help with this, and especially for making custom versions of your library for me. My fingers are crossed.... I really hope this works but at this point I don't think I have anything to lose.