Which enemies of Rome are seen as barbarians?

[M. Caecilius]

By us or by the Romans?

In the latter case, I believe virtually everyone non-Roman was considered a barbarian (except, as you say, the Greeks who actually came up with the word, and would have considered the Romans barbarians. I have not hard the term applied to neighbouring people (Samnites, Oscans, Etruscans, Marsians etc), but the Romans did tend to regard them as weird (especially the Marsians and Etruscans) or inferior (they had been defeated, after all, what more prove does Rome need of her superiority?).

As for people further away: The tribes and emerging states of northern Europe were certainly considered barbarians. The area of the Black Sea... well, ask Ovid what he thinks of the people around Tomis, even though he actually wrote a poem in Scythian. The Egyptians: Aeneid VIII 685 describes Antony's allies at Actium as barbarian. The Parthians don't fare better. With some time, it'd probably be possible to chase up references where the other peoples of Northern Africa, such as the Carthaginians, Numidians, Mauretanians, and Berbers, were considered barbarians.

Which leaves the Jews, and the smaller states around the eastern border (Palmyra, Nabataea, etc). I'd check the history of the wars and politics here, especially where Pompey or Scaurus are involved (against Nabatea), what the opinions on Zenobia of Palmyra are, and how the Romans describe the various Judean revolts. You'd also need to check, for instance in Pliny the Elder, what people thought about the Seres (Chinese?) and Indians, but so far as I remember, Rome still considered herself superior.

Note that, at least in the earlier Greek use, barbaroi does not necessarily mean uncultured. Herodotus accepts that the Persians and Egyptians are advanced cultures... but they are non-Greeks.