Is overfitting always a problem? If I test various models and the best performing model also happens to be one that appears to be overfit, is this an issue?  For example, if I have a model with 100% accuracy on the training data and 75% on the test data and I compare it with a model that has 65% accuracy on both training and test, is it a problem to select the first model?
I guess you could argue that maybe my first model could be improved in some manner so that it is no longer overfitting and thus test accuracy would also likely improve, but what if it couldn't? Is the large discrepancy between training and test error a warning that future data may not predict well? An issue of stability perhaps?
 A: A 100% accuracy on the training set may be a sign of a gross error in modeling process, not just of overfitting, but that depends on the model/algorithm used in training. Namely, predicting with a random forest classifier on the training set will give you a 100% accuracy, but that's because of RF's inner working. In this case 'fitted' values are exactly the same as the response, but that's not a problem. On the other hand if your stats linear regression model, for example, had fitted values all the same as the data points, that would be a definitive sign of gross overfitting. To answer your second question through an example -- assume your first method is a random forest (100% and 75% accurate on training and test sets, respectively) and the second method is logistic regression model (65% / 65% accuracy) -- then using RF over logistic regression would be justified. 
A: As you said, the first thing to do is improving your model and taking precautions against overfitting, but let's accept that you hadn't been able to do that. And, I'm putting aside the (probably high) possibility that accuracy might not be the best metric you should use. Your first model's accuracy on training set is 100 %, which is quite uncommon, and there is a significant gap between train and test successes. You're probably in high variance zone. A future test could result in, let's say, 40 % accuracy. For the second model, I think we can't say much. It's actually good to have close train and test successes, however 65 % accuracy, for example for a balanced binary classification problem, could be just underfit.
