I also have a site that has numerous urls with urlencoded characters. I am finding that many web APIs (including Google webmaster tools and several Drupal modules) trip over urlencoded characters. Many APIs automatically decode urls at some point in their process and then use the result as a URL or HTML. When I find one of these problems, I usually double encode the results (which turns %2f into %252f) for that API. However, this will break other APIs which are not expecting double encoding, so this is not a universal solution.
Personally I am getting rid of as many special characters in my URLs as possible.
Also, I am using id numbers in my URLs which do not depend on urldecoding:
example.com/blog/my-amazing-blog%2fstory/yesterday
becomes:
example.com/blog/12354/my-amazing-blog%2fstory/yesterday
in this case, my code only uses 12354 to look for the article, and the rest of the URL gets ignored by my system (but is still used for SEO.) Also, this number should appear BEFORE the unused URL components. that way, the url will still work, even if the %2f gets decoded incorrectly.
Also, be sure to use canonical tags to ensure that url mistakes don't translate into duplicate content.