Does Islam allows criticism on its prophets or holy personalities (definitely for non Muslims) and if yes then where lies the boundary between criticizing Prophet Muhammad (pbuh) and blasphemy?
All perfect praise be to Allah
There is a fundamental difference in both of these words. criticism and blasphemy. It must be known that all people who were not Muslim in the era of prophet Muhammad SAWW used to criticize Islam and prophet, but they all were not beheaded, only a few of them which were mocking, abusing or doing vilification about Islam or prophet were executed.
Criticism is done all time by Jews and Christians and all non-Muslims, but we don't say they all are doing blasphemy, only when some makes cartoons etc of them, or mocks in any other non-constructive/abusive/disrespectful way. Than that is considered as blasphemy.
I think this gives a basic idea of the fundamental difference.