Slight bug in JoomSEF - it doesn't pay attention to whether menu items are in the trash. Therefore, if you delete a menu item, but don't remove it from the trash (or haven't got round to removing it from the trash), the SEF URLs will reference the deleted menu item.
It's not a major issue, but it shouldn't be hard to correct.
Thanks for a great component, and I am waiting eagerly for the developer docs to build SEF extensions!