Is 'job title classification' rather a problem of NLP or machine learning?
This question has a number of parts to it.

First, you have a representation problem: what is the correct way to present textual data to your machine learning algorithm?

In this case, you chose to apply Bag-of-Words and then TFIDF scores. For English, this might be expected to produce on the order of 100,000 features, with each instance having only a few non-zero features.

If you want to go this route, you would typically also do some kind of feature selection to eliminate unimportant features from consideration. Depending on your task, you may be able to reduce the size of your input vectors quite dramatically while still getting good performance (for some tasks, to just 100 or so).

You're right that this might not be the most promising approach however.

My choice for this problem would be to use a compression classifier, like DMC. These have the advantage that they do not need any feature selection or pre-processing, and can easily handle new words or typos. They give state-of-the-art performance on tasks like spam-email classification.