Khorium Ore

By far, the fastest sure-fire way to find lots of Khorium is to fly around Nagrand on an herbalist. :-/

Khorium Ore isn't that difficult to obtain, it just needs to be actively farmed rather than searched for. What this means is the following:

Simply select a zone and start mining everything there, continually going around in circles. Every Outland vein you mine has a chance of repopping as a Khorium vein. Given that there are far less people in Outland these days than there were before Wrath of the Lich King, the chances are pretty good that you yourself are the next person to arrive at a vein when it has respawned. As long as you keep flying around mining every vein you come across and continue to do so, all the Khorium that repops is usually yours. From my own experience of mining like this in Nagrand, I usually get several Khorium veins each time I complete a circle.

I use two add-ons to help me farm it, which are great to have if you're a miner or herbalist anyhow: Gathermate and Routes. Gathermate keeps track of any veins you've come across, and you can import data from the Gathermate_data add-on so you won't have to discover everything yourself. With Routes you can then calculate the most efficient route to visit all possible spawn points in a zone, and display that route on the map and minimap. This makes the farming simply a matter of following a line and mining every vein you detect near it on your minimap.

This way it's only taken me a few hours to mine all the Khorium for my Turbo-Charged Flying Machine. Hope this helps.

I can't believe this hasn't been mentioned, but to me the best place by far is: Isle of Quel'Danas

Once you get to the Isle, there are 6 nodes up at any one time. Use the Gatherer addon or any other source to know the spawn locations of all possible nodes.
Start your circuit by doing the 3 around town then go around the isle starting from the Naga area, down to the scar, back up to the wretched.
You may get none or multiple nodes to spawn within 1 cycle, it is a rare node, therefore it's all up to the great RNG.

The whole idea of Quel'danas is that you, control, the entire zone. The whole idea of FARMING is the same thing. If you do your route right and hit all the nodes in time back to back, no one else gets the ore. Nagrand is terribly large, has the BC respawn rate of nodes (to make sure no smartass compares it to Uldum in which the spawn rate is CRAZY) and has nodes in caves which can hinder your speed. This lets other players get a chance at your nodes. If the first node you got was towards the south of Nagrand, respawned into a Khorium, and you're all the way to the north or towards the end of your route, well too bad buddy but there is still a chance someone else grabs it. If you control the zone and almost literally wait in the area for it to respawn, no one can touch it.

Don't bash or downrate, I'm just sharing the information I have gathered and now I'm on my way to make my CHOPPAH!

EDIT: I edited the post to give a better explanation of the logic and correct a few errors. Also, please note that even in Cata, you cannot fly in this zone. Azeroth BC zones have not been touched in Cataclysm. As confirmed in comments, 100% is actually still too fast for the spawn rate. So you don't need flying.