The South really wouldn't want to let that city go as it is to valuable a port to be let go. The North doesn't want the trouble of garrisoning such a large (in southern terms) city, and New Orleans would probably just rejoin the Confederacy anyways.
I just don't see the impetus for the South to give up the city. Besides, withdrawing from the city would probably be one of the matters the treaty stipulated for the Union to do.
I think we need to remember that the basis of this POD must be that the South wins after April 1862 when Farragut's fleet captures New Orleans. In August they went on to capture the state capitol, Baton Rouge and by the end of the year controlled most of SE Louisiana, an area of about 10000 sq. miles with a population of about 500000. In other words, not a small enclave but a large area that the Union could defend in depth.
It'd probably be easier to create a POD where not only does the Union keep SE Louisiana, the people in that area actually support the Union. Butterfly away Spoons Butler, and you've a great start right there. Also, the military gov't needs to garner the support of the Creole community. The Seccession constitution of 1861 was the moment when French ceased being the language of government and record in Louisiana, and that loss of cultural power still smarted. Allow a controlled reopening of the New Orleans-Liverpool/New Orleans-Le Havre sea lanes to trade. There's a fuckton load of cotton, sugar, rice that's been piling up in the area since the start of the war, and if the military gov't controls the sale, it as well as the locals will profit. Also, ships returning from Liverpool will bring in the iron and coal to keep the foundries going and help alleviate the heating shortage of the war years. (Yes, it was cheaper for New Orleanians to import their coal from England then ship it from Pennsylvania well into the late 19th century. There was just that much traffic, to the point where most New Orleanian fireplaces burnt English coal.)
However, this is a scenario that could also lead to an independent "Republic of Louisiana." Say all this happens, but the North finds itself in a bind in 1863. Lee's Pennsylvania campaign is more successful, let's say, and Vicksburg holds on long enough that Grant is forced to release some of his troops back East and the siege becomes porous if not broken. Add to that the conscription riots that were already occuring in the North, and Kennesaw Mountain, by New Years' 1864 you could see the Union ready to end the conflict. They'll still be negotiating from from a strong position, though, since they still hold almost the entire length of the Mississippi, including New Orleans, in 1860 the 5th largest city in the country and either 1st or 2nd most important port. As well, they hold almost all of Tennessee, all of Virginia west of the Appalachians and north of the Rappahannock, as well as many of the Sea Islands and port towns along the Gerogia-South Carolina coasts.
You can add to this the increased goodwill of the British and French to the Union for the reopening of the New Orleans trade links (the cotton blockade caused massive economic dislocation in Lancashire and Normandy OTL). You could see England and France putting pressure on the South to accept, if not Union control of SE Louisiana, then a "neutral," independent state at the mouth of the Mississippi, a neutrality guaranteed by all four nations (USA, CSA, UK, France). In exchange, the Union would evacuate all forces scattered along the Atlantic seaboard and give up claims to the Indian Territory. Tennessee would remain in Union hands, and Virginia would relinquish all claims to the lands north of the Rappahannock (to its source), then along a line north to the OTL West Virginia border. The boundaries of the "Republic of Louisiana" would be, strating from the east: Pearl River up to the Bogue Chitto, Bogue Chitto up to the 31st parrallel, 31st parrallel west to the Mississippi, up the Mississippi to the Atchafalaya split, and south along the Atchafalaya to the Gulf. Given the situation in southern Louisiana OTL in late '63, this would basically be in the realm of an ubi posseditis settlement. They'd be trading lands west of the Atachfalaya to Bayou Teche they'd conquered OTL in late 1863 for still Confederate-held territory on the north shore of Lake Pontchartrain to secure all the approaches to New Orleans.
That's just my (long-winded) 2¢. The longer I think about it, the more it becomes plausible, given the right circiumstances. I mean, hell, what does the South want with all dem Frog-speakin' Cat-licks anyway, huh?