Respondo separando as suas dúvidas em cada um dos termos.
Ordinal de mil milhões.
Na pág. 184 da 3.ª edição do livro de Guilherme de Almeida: Sistema Internacional de Unidades, considera-se para Portugal: o milhão (106), o mil milhões (109) e o bilião (1012).
Observemos agora os seguintes factos: É costume a última posição dum conjunto cujo total é um dado número cardinal ser representado pela mesma designação que uma das partes em que o total é dividido pelo mesmo número (ex.: «o clube está na décima posição», «pagou uma décima do valor»). Repare que o determinante caracteriza a diferença («a décima», «uma décima»).
Ora para representarmos o ordinal de mil milhões basta-nos pensar como representar a fração resultante de um total que foi dividido em mil milhões. Consideremos uma unidade dividida num milhão de partes: 1/106; se agora dividirmos uma dessas partes mil vezes: 1/103 x 1/106, teremos um milésimo de um milionésimo; ou, simplificando: um milésimo milionésimo: 1/109. Então, o ordinal de 109 será, no raciocínio acima, o milésimo milionésimo no conjunto (o último de um conjunto de mil milhões).
Bilionésimo: Na convenção que adotamos em Portugal, será o ordinal de 1012.
Bimilionésimo: Na convenção que adotamos em Portugal será o ordinal de 2 x 106 (prefixo latino bi-: duas vezes).
*"Dois milésimo", ordinal de 2 x 103: Não recomendo esta representação. A mensagem percebe-se, mas a lógica será bimilésimo. Repare que usando um termo corrente, não dizemos "dois centenário", mas bicentenário.
*"Mil milésimo": Também não recomendo. Como ordinal de 1000 x 103 seria até uma redundância, porque seria o milionésimo: ordinal de 106. Notar que se tomarmos mil milésimos de uma unidade: 1000 x 1/103, obtemos a própria unidade, um cardinal.
*"Mil milionésimo": Também não recomendo esta representação como ordinal, por tudo o que acima foi exposto. Notar que se tomarmos mil milionésimos de uma unidade: 1000 x 1/106 = 1/103 , obtemos um milésimo dessa unidade, um cardinal.
Nota Final
É preciso cuidado com as consultas na Internet. Se forem feitas em enciclopédias, ou em entidades responsáveis, merecem confiança; mas se se baseiam na pesquisa por motores de busca, deve-se lembrar que o motor se limita normalmente a selecionar preferencialmente o maior número de ocorrências; ora nada garante que estas estejam nas normas consagradas. A Internet, com todas as suas virtudes é ainda infelizmente um mundo quase libertário. Tenta-se presentemente impor alguma regulação, mas ainda não há decisões concretas.