Do you use non-ASCII characters in post titles? If you do you probably know how your links look like..
So if you don't like these links www.site.com/2008/05/-1 then this is a must-have plugin. ;)

It replaces post title's characters using a given pattern. By default it set to transliterate all Russian/Ukrainian letters to Latin, but you can set any pattern.
Example: if the title is "Привет всем" your permalink will be "privet_vsem".
You can also set it to change "Hi" to "hello_everybody" or whatever you want.