Questa frase
Vorrei aggiungere una riga sempre alla fine del datagrid, ma ogni due o tre inserimenti, la nuova riga viene creata in testa al datagrid e non in fondo.
risulta molto strana perchè non ha proprio senso che il problema si verifichi 'ogni 2 o 3 inserimenti'. O si verifica sempre, o si verifica in determinate condizioni.

Premesso che se:
a) il record viene aperto con una query senza ORDER BY
b) non viene usato il metodo Sort del recordset

è pacifico, che il recordset mostra i record nell'ordine naturale.
Questo non è una opinione, ma un fatto inconfutabile.

Ciò significa che c'è qualcos'altro che modifica l'ordine dei record.
Magari qualcosa che non ci hai detto, o di cui non ti sei accorto. Verifica bene.
A meno che tu non abbia qualche folletto informatico nel computer.

A parte la battuta,
un paio di suggerimenti:
1)
da quello che vedo apri la connessione con il cursore predefinito (lato server).
Io uso sempre un cursore lato client, è sempre preferibile (a parte quando si usano le transazioni per le quali e d'obbligo il cursore lato server).

2)
Aggiungi l'opzione adCmdText nel rs.Open.... così aiuti ADO.

3)
Ovviamente do per scontato che tu abbia
a) installato il SP6
b) referenziato ADO 2.8
...