As far as I know, there haven't been any changes that should cause that, so I can only guess...
For some Bluetooth things to work, we need to install Google Play and grant the "nearby devices" permission to Google Play Services. On Stock OS, Google Play Services already has that permission and more, so the Stock Settings app or other apps can use a Play Services API to get nearby devices.
My guess is that the devices you're not seeing on your phone are things like smart TVs that when polled by your phone advertise services your phone doesn't "know" how to handle without Google Play Services, like Cast, so it just doesn't list them.
So, if I'm right and if you're trying to find these devices on your phone using another 3rd party app, maybe you can try installing Google Play Store, then granting the nearby devices permission to Google Play Services. I doubt this would make these devices show up in the Settings app on GrapheneOS since it's the AOSP Settings app.