BroadcastReceiver 같은 경우에는 최초 실행 없이는 동작하지 않을겁니다.
해당 패키지 상태가 Stopped라 그런건데 최초 실행을 하지 않은 경우에도 Stopped 상태로 관리됩니다. 그 외에도 Stopped 상태로 변경되는 경우(TaskManager에서 킬할 시)도 있고요.
http://developer.android.com/about/versions/android-3.1.html 에 Launch Control on Stopped applications 항목 참고
위에 링크 가서 보시면 모든 브로드케스트에 Stopped 상태의 어플리케이션은 제외하도록 플래그 셋팅이 됩니다.
이때문에 리시버가 브로드케스트를 못받는거지 등록이 안된건 아닙니다.
Stopped 상태에서도 받게 하려면 FLAG_INCLUDE_STOPPED_PACKAGES 설정 해주시면 됩니다.