I've built a number of custom IValidate classes and have never experienced such issues. I have however never set anything else than ErrorMessage and PropertyName on my ValidationErrors. I usually also return Enumerable.Empty<ValidationError>(). Neither of those differences should matter though.
I had same problem as you had, I can't recreate it, but it did happen few times to me.
Now, I have changed it to return Enumerable.Empty<ValidationError>(); and tried out a couple of times with this and return null.
Every time return null gives me the problem described and return Enumerable.Empty<ValidationError>(); gives me the correct behavior.
Have you tried out EPi 7's custom validation?
The error is returned when the validation condition is broken. However, when I fix the thing that is causing the validation error, auto save always returns: "Offline, can't save" and hitting Publish, gives me the validation error.
This is the code: