Beside discovery, how about pairing? If a device isn't MFi, could an iPhone pair with it? If so, is it doable in all versions? Then what's the point of the MFi?
Yes you can discover - pair and in connect also as long as both the device supports the standard profiles (like HFP, A2DP, PAN etc) , to do these you dont need MFi. MFi is only needed if you want your app to talk to your accessory - which will be possible only over non standard profile (like a protocol / over the SPP profile) in which case you will have to build your device as per MFi.