What should I do now when this conference first sends me an "accept", then a "reject"?
Should I put any endeavor in contacting the PC Chairs and ask them to explain this strange stand? Should I explain my stand that the work has been drastically changed and improved from what it was when submitted?


I think an email to the PC would be appropriate.  Don't expect the answer to change, however, and it may very well have been an administrative oversight.  Even as a mistake, it is a relatively minor one that you don't have much control over.


  Does such a behavior make them accountable for any legal action from my side? And, is it worth for me to take such an action?


No. Their decisions aren't bound by any laws (that I know of) that could force them to honor their original email.  If you make a big deal of it, you're likely to make a bad name for yourself, regardless of the mistake being on their end.

In the end, you've now got a better paper that probably shouldn't have been published anyway.  Your changes are now in place, and you admit to having improved it.  Submit it to another conference, and move on.