Why is this young woman, in a thin cotton blouse, dark pants and boots, standing alone with a little suitcase in her hand, 50 metres from an Israeli roadblock? The morning sky behind her has a desert purity. Her uncovered hair is ruffled by a dry wind. She sets out for the checkpoint with a slow, deliberate step.

Knowing that Paradise Now is a story about Palestinian suicide bombers, we are clenched for an explosion; and so, no doubt, is the Israeli soldier before whom the woman stops at the inspection post. Their gazes lock. He rummages through her case, and sends her on her way with a tiny jerk of his head. Throughout this wordless encounter their faces remain strenuously blank but they never drop their eyes. The current of emotion between them will flow on through the movie, strangled, polluted, bitter beyond healing.

Suha (Lubna Azabal) takes a beat-up cab from the checkpoint into Nablus to pick up her car from the garage, where the movie’s two main characters, Khaled and Said, slog out their days as mechanics. Suha’s father was a famous martyr to the Palestinian cause and she was raised abroad. But despite the independence of manner this gives her, she has a little tendresse for shy Said, born in a refugee camp and stuck in the occupied territories all his life. Khaled and Said are an appealing pair in their twenties, grubby and messy-haired. When Khaled takes a sledgehammer to a rude customer’s bumper bar in a way that will lose him his job, we are already on the young men’s side, even before we have seen their faces in close-up.

What were we expecting – the grinning fanatics of Bali? Khaled (Ali Suliman) is a speedy, fine-featured fellow with clever eyes and a dry manner. Said (Kais Nashef) is juicy-lipped and dark-browed, reserved, more the brooding type. Flirting gently with Suha outside the garage, drinking tea and smoking on the hillside above the square white boxes of Nablus, they don’t look so different from young blokes we might have dealings with around here. Explosions and sirens are the soundtrack of their daily lives; they seem resigned to their limited future in the occupied West Bank.

In fact they belong to an unnamed terrorist organisation. When they visit its headquarters that evening their superior announces, to their shock and pride, that they have been chosen to carry out a suicide bombing in Tel Aviv. They are to spend one final night with their families, keeping their mission secret, then report for duty the next morning.

During that long, wakeful night, Said slips out to visit Suha. She is the character who personifies the movie’s argument against suicide bombing campaigns. Fresh from a freer life in France and Morocco, she is appalled by the cramped hopelessness, the obsession with self-destructive violence that she sees in the Palestinian resistance. With Said she is merry and sweet, keen to talk about pleasurable things of the mind. She teases him: “Your life is like a minimalist Japanese movie.” But Said is too full of his secret to be playful. He answers sombrely, “God bless you,” and wanders off into the night.

No woman’s optimistic reasonableness could prevail, for him, against the drama of what the movie shows us next: the dark dream-world of the terrorist organisation, completely male and fiercely hierarchical, marked by a series of rituals that exude a homo-erotic intensity. Next day, in the dim, cave-like hide-out, surrounded by fighters holding machine guns, Said and Khaled are shaved and shorn. They are laid out naked and bathed from head to foot as if they were already corpses; then, dressed (“like settlers going to a wedding”) in clean white shirts and well-cut black suits, they are brought to a long trestle to share a valedictory meal – an audacious subliminal flash of Leonardo’s Last Supper.

The bombs are taped to their torsos. Whichever of them goes second, says their affectionate, chubby-faced handler, should not watch the first one detonate. Khaled’s smile is sickly: “What happens afterwards?”

“Two angels will pick you up.”

“You’re sure?”

“100%. You’ll find out.”

What they find, of course, is not the clear and simple death they have been prepared for. Somebody has betrayed them, and out there on the pale, rocky roadside near the razor wire things go catastrophically askew. Khaled and Said are separated in the confusion. Khaled makes it back to headquarters and is stripped of his bomb (and his honour) but Said, panicking and angry, is on the loose, roaming back and forth across the border, wired to explode. Suha and Khaled have to find him before the organisation eliminates him.

Paradise Now must have been hell to make. Who is director Hany Abu-Assad’s audience, and what knowledge can he assume it to have? He has to pack his story with essential background but not deliver lectures. Everybody in the world will be breathing down his neck: his characters can’t develop according to each one’s inner logic but must serve what he wants his movie to say.

Said’s father, it turns out, was executed as a collaborator when the boy was ten. OK – we may hate what Said does, but we can join the dots. Ali Suliman, as Khaled, though, turns in a performance almost more nuanced than the movie can handle. His screen presence has a shivery sensitivity that’s irresistible to a thinking heart. Said’s morbidity we can at least intellectually understand, but why is Khaled, this droll, vital young man, so eager to blow himself and a busload of strangers sky-high? Could one wild argument with Suha in a speeding car really change his mind? I longed to understand more about him than director Abu-Assad could afford to tell me.

These are the problems all political art has to wrestle with. Paradise Now may veer between genres, and it may not answer all our unhappy questions; but it takes us on a thrilling ride, and some of the things it shows us I will never forget.