I think i figured this more or less figured out (at least in concept).
To handle this I think I would just need to create a custom Kendo validation rule something like this:
return $(input).data("remote-msg") != null;
When the AJAX call fails, I'd then simply stick data-remote-msg attributes on the corresponding DOM elements, call kendo.validate, and then remove data-remote-msg from the various attributes (so I can call the server method again).
Haven't actually tried this yet, but I think it should work.