Diferencia entre Android ID y ID de dispositivo

Mientras que tu pregunta se enfoca en un problema de desarrollo (que está fuera de tema aquí), la respuesta es relevante para los usuarios también, así que voy a responder:

• DeviceID: Este es el serial del dispositivo, el cual debería persistir incluso después de un restablecimiento de fábrica.
• AndroidID: Este se establecerá en el primer arranque (ya sea con un dispositivo completamente nuevo, o después de un restablecimiento de fábrica). Como se implica, no sobrevive a un restablecimiento de fábrica
• Existe un segundo "Android_ID" el cual es generado y utilizado por el Marco de Servicios de Google (GSF), y por lo tanto a menudo referido como "ID de GSF". Se comporta básicamente como el AndroidID mencionado anteriormente (por ejemplo, no sobrevive a un restablecimiento de fábrica), y coexiste con él.
• Además, está el GAID (ID de Publicidad de Google), el cual puede ser restablecido por el usuario a través de la aplicación Configuración de Google.

Durante la "operación normal" (es decir, siempre y cuando no restablezcas tu dispositivo a la configuración de fábrica o restablezcas el GAID), todos estos IDs pueden ser utilizados para identificar el dispositivo. Al usar múltiples usuarios (a través de perfiles de usuario) en un dispositivo, todos excepto el DeviceID incluso identificarían al usuario (perfil).

Hasta donde sé, todos esos IDs están disponibles en todas las versiones de Android (al menos en las que son actualmente relevantes, es decir, GB/2.3 en adelante). Los dos últimos obviamente solo si se instalan las GApps, por lo que en dispositivos que ejecuten una ROM personalizada sin GApps, podrían no existir.