The posters are still up, showing the face of Gilad Shalit, the boy soldier freed last week after five years hidden in the dark. "How good it is to have you back home," runs the slogan, appearing on the side of shopping malls in Tel Aviv and on lampposts in Jerusalem. Shalit's return has enabled Israelis to walk with an unaccustomed spring in their step, despite their fear that the price was dreadfully high.

It should go without saying that Israelis would have preferred a one-to-one exchange, releasing a single Palestinian prisoner, rather than more than a thousand – many of them guilty of horrendous acts of violence – in return for Shalit. But, contrary to what some have suggested, it was Hamas, not Israel, that set that 1:1000 exchange rate; it was Hamas, not Israel, who decided that the freedom of a single Israeli was worth the freedom of a thousand Palestinians.

Yet the boost at Shalit's return is unlikely to last long. Just as the sight of his emaciated face and sunken eyes on every front page confirms that the damage of his captivity will haunt him for years, so Israelis who yearn for the security that can only come with an accommodation with their neighbours know there is no remedy imminent for them either. Except now the familiar pessimism comes with a twist.

While their own government has next to no strategy to resolve the conflict, it is now the Palestinians, so often buffeted by events, who have a plan and are pursuing it. The problem is that both strategies, old and new, are insufficient.

Start with the Israeli position. A series of conversations with senior figures in the Israeli government reduces to a single public message: Israel wants to return to direct talks with the Palestinians without preconditions. What's more, colleagues of the prime minister, Binyamin Netanyahu, point to a series of statements and signals, overlooked by both the Palestinians and world opinion, which indicate that, if Netanyahu were engaged in a serious face-to-face process, he would push for a genuine agreement.

One well-placed insider said that in the prime minister's office the man with the highest hopes for negotiations is the prime minister himself, imagining that, when it came to it, he and Palestinian president Mahmoud Abbas could make a breakthrough: "He puts himself in the other guy's shoes, thinking that 'maybe he'll take the jump with me'." To that end, the Netanyahu team tells me, they have repeatedly sought to draw Abbas into talks. Every attempt has been rebuffed, they say, "the door slammed in our face".

There are multiple problems with this account, but they all come down to a single word: credibility. For every encouraging smoke signal sent out by Netanyahu – aides mention his talk of "creativity" in resolving the radioactive issue of Jerusalem – there is at least one telegraphing an opposite message, often in the very same paragraph: that promise of "creativity", for example, came with a warning that Jerusalem must forever remain the undivided capital of Israel, thereby closing the door on a key Palestinian demand.

Nothing renders Netanyahu's offers of peace talks less credible to Palestinian ears than settlement building. I saw for myself the expansion of, among other places, the town of Beitar Illit across the Green Line that separates pre-1967 Israel from the West Bank. With some 35,000 residents, Beitar Illit now hems in the Palestinian village of Wadi Fukin, choking off all future growth. Israelis say that such building does not connote bad faith: almost all of it is under way in blocs that will "inevitably" be allocated to Israel in any eventual peace deal – in return for land from inside Israel-proper – and that in previous negotiations Palestinians have conceded as much. But such thinking breaks a necessary rule of peacemaking: one side cannot bank concessions by the other until the entire deal is done. And no deal was done. Until it is, expanding settlements in occupied territory – recognised as illegal by almost every country except Israel – is bound to undermine any call for the Palestinians to come to the table. As Husam Zomlot, a senior figure in Fatah, put it to me in Ramallah: "You can't have discussions about how we are going to share a pizza, while one side is eating the pizza." This is a problem that predates Bibi.

Palestinians say this has been the story of the 18 years since the Oslo accords of 1993: endless on-and-off talks, while the material facts on the ground – from new roads to restrictions on access and movement – change and the settler population more than trebles. It is this which, above all, makes the call to resume talks not credible to Palestinian ears: why should they sit around talking for another 18 years, watching as more of their land is nibbled away? Accordingly, the Palestinians have devised another strategy. They plan to rely no longer on direct negotiations which they believe are hopelessly asymmetric, the power tilted so heavily in Israel's favour. Those I spoke to insist there is no plan to return to violence, believing that the second intifada, with its suicide bombings of Israeli buses, pizzerias and discos, proved totally counterproductive – triggering an Israeli military response that rolled back not the occupation but most of the gains the Palestinians had made in the previous decade, destroying much that had been built up.

The new Palestinian strategy will involve neither "armed struggle", nor a return to "meaningless, open-ended negotiations". Instead it will try to deploy other tools. The first is "internationalisation", seeking to change the Israel-Palestine conflict from a bilateral dispute between the two parties into a problem for the world community to resolve: hence last month's statehood application to the UN and a current request to join Unesco. The aim is to ratchet up international pressure to such a degree that when the two sides do eventually return to the table – and Zomlot is adamant that "without negotiations this conflict can never end" – they will be, if not equally powerful, then closer to parity than ever before.

And there could be an additional pressure. There is hopeful talk of a "Palestinian spring", a popular movement demanding independence that world opinion would find hard to oppose, one inspired by the first, stone-throwing intifada begun in 1987 rather than by the murderous second one that began in 2000. Such an uprising would also put pressure on the Israeli government to make the concessions necessary for peace, much as the first intifada pushed Israel into the Madrid and Oslo processes.

There are problems here too, starting with the fact that the first target of a Palestinian spring could well be the unreformed, still-corrupt Palestinian Authority – and that an initially nonviolent effort risks spiralling out of control. As for internationalisation, just as years of talks have not brought Palestinian independence, countless UN resolutions have not achieved much tangible for the Palestinians either. One diplomat says the old Israeli strategy and the new Palestinian one boils down to this: the Israelis want a process but no peace, the Palestinians want peace but no process. That may be glib, but it's clear both strategies are incomplete.

What's needed is either for Netanyahu, if he is serious, to make a gesture large and surprising enough to overcome Palestinian suspicion and render him credible – or for the international community to take charge of a refashioned peace process, gripping it the way London and Dublin oversaw the Northern Ireland negotiations. Either way, what is currently on offer is not enough – and will mean the end of this unending conflict slipping ever further out of sight.