The best candidate is the Roman fort on the Farasan Islands in the southern Red Sea, which hasn't gotten the attention it deserves. Roman control of this area was completely unknown until the 2004 publication of an inscription attesting to the presence of a detachment of the Legio II Traina Fortis and auxiliary troops on the main island in 144 CE. The inscription reads as follows (image and line drawing here), based on the edition of M.A. Speidel 2007, reproduced with an English translation in Speidel 2014:
Imp(eratore) Caes(are) Tito Ael(io) Hadr(iano) | Antonino Aug(usto) Pio, pont(iice) | maxim(o), trib(unicia) pot(estate) VII, co(n)s(ule) III, | p(atre) p(atriae), vexill(atio) leg(ionis) II Tr(aianae) Fortis | et auxil(iares) eius caṣtr[a sub - - - ] | Avito ̣praef(ecto) Ferresani poṛṭụṣ ̣(?) | et Pont(i) Hercul(is) fec(erunt) eṭ ̣ d[̣ed(icaverunt)].
3: maxim(o) instead of max(imo) ed. pr. and Speidel 2007.
"Under the emperor Caesar Titus Aelius Hadrianus Antoninus Augustus Pius (= Antoninus Pius), high priest, in the seventh year of his tribunician power (= 144 CE), consul for the third time, father of the fatherland, a detachment of the Legio II Traiana Fortis and its auxiliaries built and dedicated a fortified camp [under . . . ] Avitus, prefect of the harbour (?) of Ferresan and of the Sea of Hercules."
This is the building inscription for the camp, giving the precise year of its foundation and the units involved in its construction. The project was overseen by a certain Avitus, called "prefect of the harbor (?) of Ferresan and of the Sea of Hercules." Besides the interesting cultural mapping of the Red Sea as Hercules' territory (like his famous pillars at the entrance to the Mediterranean), the geographic description shows that this prefect was not only a military commander, but also a civil administrator, like his counterpart the praefectus montis Berenicidis who controlled Egypt's Eastern Desert. In other words, the Farasan Islands were part of the Imperium Romanum, at least in the middle of the second century.
The nearest known Roman settlement was the port of Berenike on the Egyptian Red Sea coast (see Sidebotham 2011), some 1,000 km to the north of the Farasan Islands. On the other side of the sea, the Roman province of Arabia extended at least to Hegra (modern Mada'in Salih, Saudi Arabia; D. al-Talhi and M. al-Daire 1995), but that's almost 1,200 km from the Farasan fort. Under Augustus, a Roman army made it to Marib in modern-day Yemen, south of the Farasans, but this expedition ended in disaster (Strabo 16.4.22 ff. and Dio 53.29.3 ff.) and it is not known if any garrison was left behind or if further expeditions were made in the area. A bilingual Greek-Latin funerary inscription for a Roman cavalryman named P. Cornelius was found in nearby Baraqish, which has been connected to Gallus' expedition mainly because no other military activity is known in this area.
It cannot be ruled out, of course, that further discoveries will modify our picture of Roman rule in the Red Sea area or beyond, but for now the camp on the Farasan Islands looks to be the furthest outpost of the Roman Empire.
The best overview of Roman control of this region is Speidel 2007 (in German), but for the larger context and Indian Ocean trade Sidebotham 2011 is an excellent resource.
Sources: M.A. Speidel, "Außerhalb des Reiches? Zu neuen lateinischen Inschriften aus Saudi-Arabien und zur Ausdehnung der römischen Herrschaft am Roten Meer," ZPE 163 (2007), 296-306. M.A. Speidel, "The Roman Army," in C. Bruun and J. Edmondson (edd.), The Oxford Handbook of Roman Epigraphy (Oxford 2014). S.E. Sidebotham, Berenike and the Ancient Maritime Spice Route (Berkeley/Los Angeles/London) 2011. D. al-Talhi and M. al-Daire, "Roman presence in the desert: a new inscription from Hegra," Chiron 35 (2005), 205-217. F. Villeneuve, "Une inscription latine sur l'archipel Farasân, Arabie Séoudite, sud de la mer Rouge," Comptes-rendus des séances de l'Académie des Inscriptions et Belles-Lettres, 148e année, N. 1, 2004. pp. 419-429