The codex says it is depreciated. As a long time plugin user, I know how annoying it is when plugins don't clean up after themselves, is it's deprecation indication that it is necessary?
If the theme or plugin that adds a widget or sidebar is removed, then essentially it's removed from the system, what is not cleared out on deactivation/removal is widget data that's stored in the option table(applicable to widgets, not sidebars).
If a sidebar is removed, any widgets that were previously in that sidebar i believe get moved into the inactive widgets group, however i can't see WP doing any clean up to remove widget data from the options table(one row in the table per widget if you're curious).
I did a quick test, commented out all my registered sidebars, verified i couldn't add widgets, i see this on the widget page.
I then fire up PhpMyAdmin and check the options table, and can see various widget entries still, eg.
So it's my impression that only thing you should ever need to clean up is widget data from widgets that may not exist on the installation anymore, ie. data will remain in the options table even when a widget is no longer registered(i also tested unregistering/removing custom widgets i have, the data remained).
Correction: The key is derived from this part of the widget class registeration code, but prefixed with
Of course it's unlikely you'll know the name of widgets that get removed from the system, i just wanted to be accurate in how the option key names are determined for widgets.
Hope that helps.
Posted incase it's useful to someone..