Palestinians have never recognized Israel's right to exist. They have recognized Israel's existence but not its right to exist. In fact Abbas has said the PA will never sign an agreement which includes recognition of Israel as a Jewish state. Recognition of Israel as a Jewish state is no different than recognizing Egypt as an Arab state or Iran as a Muslim state or Syria as an Arab state and so on. Non-Arab and non-Muslim rights in those countries can be maintained and protected, unless of course you are implying that non-Arab and non-Muslim rights are not maintained or protected in Arab and Muslim countries, which would be a heck of an admission by an Arab and Muslim toady.