Turns out it was easier than I thought. In com.apple.Bluetooth.plist, there's a CoreBluetoothCache key containing a dictionary with some cached services and stuff. The tricky part was editing the cache without blued writing all over it. Anyway, this is the way to go (in Terminal):
sudo defaults write /Library/Preferences/com.apple.Bluetooth CoreBluetoothCache -dict
sudo launchctl unload /System/Library/LaunchDaemons/com.apple.blued.plist
sudo launchctl load /System/Library/LaunchDaemons/com.apple.blued.plist
After this, CoreBluetooth actually rediscovers the services and reads the characteristics the right way.