I perceive "come across" as a verb, and Googling finds sites that seem to agree with me. I realize that "across", alone, is a preposition, but the phrase "come across" is a different creature.
That's correct. "To come across" is an idiomatic verb phrase, which means a) it's pretty much fixed, and b) words in it don't necessarily have their usual classes (in fact, it's often not possible to parse an idiomatic phrase in terms of individual word classes).
