In Android 5.0, BLE doesn't use static MAC addresses anymore, but the MACs change after intervals, using a method called IRK and public key cryptography.
Is it possible to uniquely identify an Android phone in a way that can not be spoofed by the user of that phone, or has that become completely impossible now unless the other side co-operates?
No, it is not possible. That's the whole idea of using IRKs: only bonded devices can identify it after the address changes. For those who do not possess the IRK (because they have not bonded), it would always appear as a completely new device (hence the privacy).