Yes, MCID is cookie based. While it isn't perfect, it's a major improvement over the legacy solution specific identification.
You can accomplish cross device targeting if the user logs in and you set the Customer ID. Otherwise, you are correct if a user uses two different devices and does not log in, there is no way to know they are the same user. This problem is not unique to Adobe solutions.