The optimization problems which I am familiar with (e.g. the Traveling Salesman Problem) are such that approximate solutions to these problems are still quite useful.
I'm wondering, however, if there are real-world optimization problems for which approximate solutions are useless? Or, to put it another way, are there any real-world optimization problems for which the only solution that is beter/more useful than any other is the optimal solution, and all others are equally bad/useless?
After thinking about it a bit I think that problems in PPAD may be interesting to you: http://en.wikipedia.org/wiki/PPAD_(complexity)
There are a few PPAD-complete problems: Nash equilibria, Finding Brouwer Fixed Points, and End-of-the-Line. I think that you can see the common thread among all of these: we know that the object exists (unlike in SAT or the decision version of TSP).The thing about approximating a Nash equilibrium (say a mixed equilibrium in a symmetric game) is that any solution but the exact equilibrium will result in continued play or possibly even a loss by proceeding from the approximated point of equilibrium---the approximately best strategy. So, unless one can make the approximation bound incredibly small the prospect of approximate Nash equilibria seems dubious. One might also ask whether there are problems such that the existence of approximation algorithms implies something about an entire class of problems....
Suppose we have an $N-$player fair game with symmetric utility functions. Let the space of strategies for player $i$ be $D_i$. Mixed strategies for player $i$ can consist of subsets of $D_i$. In an $N-$player game call a strategy profile $\vec{V} = \{v_i\}_{i=1}^N$ an $\epsilon-$approximate Nash Equilibrium if for all players $i \in \{1, \ldots, N\}$ and all actions $a \in v_i$ $$\mathbb{E}\left[ u_i(a | \vec{X})\right] \geq \mathbb{E}\left[ u_i(b | \vec{X})\right] - \epsilon, \; \forall b \in D_i$$ where $u_i$ is the utility function for player $i$ and the expectation is over the weights that the remaining players put on their mixed strategies. A lot of games and actually a lot of real-world scenarios turn out to have mixed equilibria, but that isn't the focus of this response.
Currently the smallest known value for which there is a partially polynomial time $\epsilon-$approximation (exponential in the approximation accuracy) is $\approx .333$ for normalized utility functions, i.e. $\operatorname{Ran}(u_i) = \left[ 0,1 \right]$. Furthermore, if there were to be a fully polynomial time algorithm, ie. $O((1/\epsilon)^d P(N))$ rather that $O(N^{1/\epsilon})$, then $PPAD \subset P$ which is a big deal. So as it stands either the approximations are bad or some hierarchy collapse happens---even then the usefulness of the approximation is very questionable.
If you are still convinced that approximate Nash equilibria don't quite fit the bill I suggest looking at End-of-the-Line (explained in the wiki article I attached).
For more on this wonderful subject I suggest Noam Nisan (and Co.'s) great book Algorithmic Game Theory.
You can take for example the problem of sparse linear regression. Given a response variable $Y \in \mathbb{R}^n$ and a design matrix $X\in \mathcal{M}_{n,p}(\mathbb{R})$, you want to statistically estimate a sparse vector $\beta \mathbb{R}^n $ such that $Y=X\beta+\varepsilon$ where $\varepsilon$ is an isotropic Gaussian noise.
To enhance sparsity, a natural estimator is given by penalizing the least squares with a $\ell_0$ term : $$\hat{\beta} \in \operatorname{argmin}{\{ \left \| Y-X\beta \right \|_2^2+\lambda \left \| \beta \right \|_0\}} $$ where $\left \| \beta \right \|_0$ is the $\ell_0$ pseudonorm of $\beta$ (i.e. the number of nonzero coefficients in $\beta$) and $\lambda >0$ is a tuning parameter fixed beforehand. This procedures is statistically quite efficient, but is unfortunately NP-hard.
A simple relaxation of the problem is obtained by replacing the $\ell_0$ term by a $\ell_1$ penalty: $$\hat{\beta} \in \operatorname{argmin}{\{ \left \| Y-X\beta \right \|_2^2+\lambda \left \| \beta \right \|_1\}} $$ which is known as lasso, or basis pursuit. This relaxed problem is convex, solvable in polynomial time, and enhances the sparsity of the solution. A lot of work has been conducted in recent years to show the statistical efficiency of this relaxation (see for example the this article by Candès & Plan).
However, as you can see in this working paper by Lin, Foster & Ungar, the relaxation can, in certain (pretty rare) cases, give results infinitely worse that the NP-hard problem. In other words, approximating the optimization problem can lead to useless solutions.
Candès, E. J., & Plan, Y. (2009). Near-ideal model selection by ℓ1 minimization. The Annals of Statistics, 37(5A), 2145-2177.
D. Lin, D. P. Foster, and L. H. Ungar. A risk ratio comparison of ℓ0 and ℓ1 penalized regressions. Technical report, University of Pennsylvania.
