RadFormDecorator should work properly with RadAjax as it is able to detect partial page updates and re-decorate the updated area. The following online demo demonstrates this functionality (albeit not with RadAjax but with UpdatePanels):
We also tested locally using RadFormDecorator, RadGrid with checkboxes and RadAjax and all worked fine.
Is it possible to open a support ticket and send us a sample project that demonstrates the issue, so that we example it? We are getting ready for the Q1 SP2 to be released next week, and if indeed there is a problem with the RadAjax interoperability, there is a good chance that we fix it if we receive a repro from you on time.
the Telerik team