Browsing through the source of Datatable, as explained by kgiannakaki. The method will append all new data rows to the end of the table as it should.
The reason for the "random" behavior, is as each time a new row is added the method will perform a "redraw" of the entire table unless otherwise specified. When this does so the table is run through multiple features such as filtering/sorting etc etc ... and completely rewritten to the page. Essentially I am going to guess you are adding random bits of data into new rows which may be creating the "random" effect, whenever a new row is added.
You can easily disable table redrawing by adding a second parameter in the fnAddData call which needs to be set to false.
$(this).fnAddData(data, false);
If this issue still persists I would file a bug for this issue, as their is no other reason for this behavior.