UN Secretary General Kofi Annan has said it is too early to definitively say whether Syria has withdrawn all its troops from Lebanon.
It is not yet clear whether Lebanon has full control of its territory
In a report to the Security Council, he said he had received a letter from Syria saying full withdrawal was complete - claims the UN is examining.
In September, the Security Council passed a resolution calling for foreign forces to be withdrawn from Lebanon.
The council is due to discuss Mr Annan's report later in the week.
A UN team has just gone to Lebanon to verify the withdrawal of all Syrian troops, military assets and intelligence.
In his report on the implementation of the resolution, Mr Annan pointed out that other UN requirements had still not been met.
These included the extension of full Lebanese control over the south of the country - which used to be occupied by Israel - and the disarmament of the Hezbollah militia.
SYRIA IN LEBANON
Military intervention began in 1976
30,000 troops in Lebanon during 1980s, 14,000 by 2005
Syrian forces helped end Lebanese civil war in 1990 and maintain peace
Calls for Syrian withdrawal increased in 2000 after Israeli pull-out from southern Lebanon
UN resolution calling for foreign forces' withdrawal in Sept 2004
Mr Annan said several incidents had shown the government did not have full control of all its territory and he added there had been no change in the position of the militias and that armed vigilante groups were now being set up as well.
The UN chief said that according to the Lebanese and Syrian governments assertions that Syrian military intelligence had taken up new positions south of Beirut were untrue.
Mr Annan said Lebanon had reached a critical juncture and it was time for all parties to set aside the vestiges of the past.
He called for free and fair elections to be held on schedule, warning any delay would threaten the security, stability and prosperity of the country.
Pressure for Syria to leave grew after the assassination of former Lebanese Prime Minister Rafik Hariri in February.
Damascus has denied any role in the death of Hariri, who was killed by a car bomb in Beirut, but the event prompted giant protests calling for the Syrians to go.
Syria's troops in Lebanon - which at one point numbered up to 40,000 - were scheduled to leave completely by 30 April.
Earlier on Tuesday, a parade of about 200 Syrian soldiers in the Bekaa Valley marked the end of the 29-year deployment in Lebanon.
Soldiers received medals and shouted support for Syria's president before marching off to the strains of a Lebanese army band.