If you didn't know, Google even added a special API in Android for Apps to use to get device IDs, IMEI included. The very point of it is to allow tracking by Apps.

In Android 6 they even made a special callback result to indicate that the user has refused to give his permission rather than indicating that modem/phone ID wasn't found.

Clearly they are aware of this and do that deliberately.