If it makes you anxious, make a flexible booking for a hotel that does open up its rooms earlier -- usually international chain hotels, in my experience -- and cancel later when you find better options. Bookings in Japan are generally 100% cancellable with no charge until 2-3 days before check-in time.