What is the best way to deal with 404s that are all trying to point to the same location.

I started getting 404s showing up in my Google Webmaster's Tools from a site linking to a specific category but with oriental characters at the end of the url. So Something like this:

http://example.com/category/puppies%EF%BC%9A.textwidget%E8%A6%81%E7%B4%A0%E7%B7%A8%E9%9B%86

Google Webmaster says that there are about 120 of these links and I can imagine there will be more to come. What is the best way to handle these links? I have heard 301 redirecting too many links can cause Google to ding the site but I don't want this site to continue posting broken links. Any help on this would be appreciated. Thank you.