Uh, either you did not select the right option or you have something wrong in your Firefox setup, the address bar history (browsing history actually, since everything has been merged) is deleted as always, checking "Navigation history", which is the first option in the "Delete private data" dialog. I just checked and it works :-)
If Mozilla removed that option, there would be a massive attack over their headquarters