Finally after spending a couple of hours, I was able to understand the code of org-refile-get-location \o/. The detailed bug report helped me to understand the issue. I'm attaching a patch here which should fix the problem, it has other details as well. I have tested a few basic scenarios as mentioned in the report.

OTOH, I haven't signed the FSF Copyright assignment yet, should I do it before this gets merged or it can be done later?