> What passport do you use? (UK passport holders shouldn't need to apply for a
> visa in advance to go to Israel. If we do need them I'm in deep trouble)

If you've previously been refused entry, that usually makes you
ineligible for visa-free entry in the future.

^^ This. You should be fine if you have never travelled in the region before.

Usually it goes the other way (certain countries are funny about Israeli stamps) but in this case they were very funny about it.

Tom