non-text characters like "!", etc. causing 404's

SEF advance running in a J1.5.26 site. I just checked the logs and see lots of 404 errors.

For example:

This is the Bad requested link (direct request):
artists-bill-of-rights.org/competition-l...-games,-gov,-canada/

This is the working SEF advance URL:
artists-bill-of-rights.org/competition-l...-games,-gov,-canada/

Bad requested URL:
artists-bill-of-rights.org/competition-l...,-%2523uk,-%2523gov/

Good SEF advance URL:
artists-bill-of-rights.org/competition-l...h-council,-uk,-gov,/

Bad requested URL:
artists-bill-of-rights.org/about-us/abou...what-can-you-do?%2F/

Good SEF advance URL:
artists-bill-of-rights.org/about-us/about-us/what-can-you-do/
(This had a question mark at the end and I removed it and created a redirect from any requests that had the question mark)

Requested Bad URL:
artists-bill-of-rights.org/news/campaign...-the-law-%20-part-1/

Referred from:
translate.google.com/translate_p?client=...hBNNDvMI5uArDEEOI4dw

Good SEF advance URL:
artists-bill-of-rights.org/news/campaign...-the-law-%11-part-1/

Even search engines are turning up 404s.

Can someone help me begin to sort this? Where are these bad requests coming from?

PHP 5.2.17
Joomla! 1.5.26
DB collation: utf8_general_ci

Obviously I'm in over my head.

Can anyone get me started on the above?