Animation Shop, que es un complemento de Paint Shop Pro te lo hace también. De todos modos, he encontrado gif que consigo comprimir mas de un 50% y otros en cambio lo que hacen es aumentar de tamaño con este programa, aún ajustando los parámetros para comprimir al máximo.
Saludos
