Methods and systems for IMEI registration are provided. In accordance with exemplary embodiments of the present invention, when an IMEI registration fails due to a network failure, the mobile station implements a back-off algorithm for future IMEI registration attempts. Specifically, the present invention provides a back-off algorithm which determines a different amount of time for the time period between each unsuccessful IMEI registration.