Success but with one question.
Finally, I put 20MHz clock. It started working with absolutely no problems.

This leaves me with one MAJOR question - Is there any way, I can run the whole show at 4MHz, any settings I missed or anything I can do. I have got no extra pins on my PIC to put an external oscillator, I want to confirm the answer to this question before I start again and choose another suitable PIC. My task will get much much easier if there is a way to run it at 4 Sweet Megahertz.

Many many many thanks to you guys for trying to helping me out on this. This forum is the best.