Someone with a similar (but different) challenge posted recently:
Best way to Fukutoshin Line @ Shinjuku-sanchome?

That person had thought about shipping luggage to a nearby store. I wonder if that's an option for your parents.

I would also suggest calling the cruise company and asking if they have arrangements for receiving luggage. It seems to be a common concern - I can imagine that any Japanese customers would want to be able to do this.