Does a strong exchange rate always mean a cheap holiday regardless of where you are from and going? As question title states, does going from one country with a much stronger exchange rate, or a moderately higher exchange rate, in comparison to a country you visit always mean you get more bang for your 'buck'?
If by "stronger exchange rate" you mean you get more units of the local currency for a dollar (or whatever currency your home country has) then no, not at all. In fact, in economics the term "stronger exchange rate" is not used in this context. People sometimes say that currency A is growing stronger compared to currency B, but this only means that the exchange rate is improving, it does not say if the number is large or small.

If you want to know whether you get more bang for your 'buck' then what matters is purchasing power: how many goods in the foreign country you can buy for the currency units you got for your dollar. Assuming an exchange rate of $E$ units of currency X per one dollar, and a foreign price $p^*$ for some good, you can buy $E/p^*$ units of said good. You can compare this number for different countries to see how far your money will go. 

The comparison is made somewhat difficult by the fact that the ratio will probably differ for different goods. Economists usually construct price indices to go around this problem. However no price index is perfect, each one is made to suit a distinct purpose. Basically you would have to look at the price of the goods that you are likely to buy during your stay.