Not very difficult, seriously.
I hesitated to complain to the Yahoo! customer care, but they were really fast in responding once I reported the matter to them. They only took about 6hrs to let me reset my password. The story with google was a little different, they took time but never responded - and even before they responded he hijacker gave me my gmail account back too. Well, how the hijacker himself helped me gain access to my account is another story. (Did I mention that the hijacker sent me a message from yahoo messenger which said “prasad your gmail and yahoo account gone with the wind iitian”)
A little information about the hijacker: Used a dial-up connection to Internet from a CDMA phone. The hijacker used “niharks@yahoo.com” which according to the actual Nihar was hacked about 3 years ago - trust him or not - I did for various reasons.
How difficult is it to get to the hijacker? A complaint to the police and requesting the logs from VSNL could possibly help me get the CDMA phone number - how much closer will I want to get! Will try my luck, but without a complaint to the police 
I am Prasad Sunkari,
co-founder of