If someone call me and ask for my adress I would give it, but my first question would be, why do you need my adress? And if my birthday is in 2 weeks I would understand why and the suprise would be ruined.
But it seems as this is the only solution, its really strange as most countries have whitepages and/or the possibility to reverse phonenumber check to get the adress, but in some cases Japan seems to be 10 years after in development.