Одна из версий: поговорка появилась после татаро-монгольского ига, в период возвышения Московского княжества и укрепления централизованного государства, когда шел процесс поборов с других городов и княжеств, в Москву посылали из них челобитчиков. Эти просители со слезами на глазах, которые они пускали для пущей жалости, начинали примерно такую песню: "Бьем челом тебе, царь-батюшка! Совсем одолели нас твои слуги! Рассуди по справедливости, защити от неправедных поборов!"
Царь-батюшка таких жалобщиков часто наказывал, да так, что другим неповадно было. Так и родилась поговорка "Москва слезам не верит".
Её трактовка отлично описана примечанием к пословице у В.И. Даля:
"т.е. никого не разжалобишь. Все чужие".