When I display a recordset that is sorted with a "order by" clause and append a new record and the new record gets sorted in the recordset, the recordset gets out of sync. How can I avoid that?

In your OnAddedNewRecord, you should call Redraw(GX_INVALIDATE). This will make sure the whole grid gets redrawn and reflect the new records order.

Example:

void CGxqueryView::OnAddedNewRecord()
{
       CGXRecordView::OnAddedNewRecord();
       Redraw(GX_INVALIDATE);
}