Here are a couple of interesting points (or maybe not).

I renamed the two "Older" folders on my Mac a few hours ago. I just checked Sparrow on the iPhone and it showed I now had the renamed folders AND the originals. The same was reflected on my Mac.

So within the past few hours, after renaming the folders, new folders were created magically with the old names.

I've now removed Sparrow from the iPhone and deleted the folders using iOS default Mail app. Within a minute of doing this, my Mac's Mail reflected the change, the folders were gone. I checked the Mail folder inside my Library folder on disk and the "Older" references were gone from there as well. Confirmed with SquirrelMail web mail and the folders are not showing up there either.

Now we wait again to see what happens... Meanwhile time to try ssh...