Cannot delete shipping method on an order

 Hello,

On a booked order or an order that has already been saved, we get an error while trying to delete the shipping method. It says ship method code or carrier service id is not valid. On some orders we can enter shipping method and delete it and delete the method on the line, but other orders we get an error. Metalink suggests patch needs to be applied, I couldn't find any other information. Is there another resolution to this error?

Thanks in advance.