Just for other people reading this question. We have narrowed down the issue by implementing
-(void)application:(UIApplication*)application didFailToRegisterForRemoteNotificationsWithError:(NSError*)error
After that it turns out that the app was signed with wrong provisioning profile. Simple things like that are getting missed :)