Techniques for showing optimality of given packing There are some natural packing problems that have been asked in mathematics. Some of them are:
1)How many balls can be placed with in a cube?
2)How many equidistant points can be place on the surface of a sphere?
3)How many code points can one have asymptotically for a length n code with minimum distance(itself defined in various ways) d over an alphabet of size q?
There are many other generalizations to packing in spaces of different characteristics.
My question is given a packing, what are some of the most useful (avoiding exhaustive search) techniques available to show that packing is NOT optimal?
 A: Usually the best way to show a packing is NOT optimal is to construct a better one. 
You might try various heuristics, or non-exhaustive search methods such as simulated annealing, tabu search, or genetic algorithms.
A: My knowledge is limited when it comes to general combinatorial packings. But the kind of problem OP described is important in coding theory, where the difference between proving the existence of a good packing and explicitly constructing it (along with a practical decoding method) can be significant.
Assuming you come up with an error-correcting code and an efficient decoding method, if you would like to know if it's optimal or not as a packing, basically you need a good lower bound on optimality as a packing that potentially shows that you could do better or an upper bound that your code happens to achieve (so you can prove that yours is an optimal example in one sense of optimality). Since you want to show that your code is not optimal, we ignore the latter case.
Assuming that the alphabet size $q$ is fixed and that the parameters you care are the length $n$, number $k$ of codewords, and minimum distance $d$, one trivial way is of course to check all known codes ever constructed that have the same $n$ and $k$ and see if at least one of them has larger minimum distance $d$ than yours (or fix $n$ and $d$ and see if there is a known code that packs more codewords, or fix $k$ and $d$ and check if a known code can achieve them at a shorter length).
Certainly the above statement is trivial and hardly a "mathematical" method for proving that your code is not optimal. But you might be in a situation where no one has come up with explicit constructions for codes that have the exact same $n$ and $k$ (or $n$ and $d$, or $k$ and $d$) as yours. So you need a more general way to mathematically prove that you could do better if you try hard enough.
The Gilbert–Varshamov bound is a well-known, general lower bound on the size $k$ of a code of length $n$ and minimum distance $d$. You can fix a different pair of parameters to show non-optimality, too. Roughly speaking, this bound is proved by showing that there exists a certain greedy algorithm for gathering codewords that gets you at least a certain number of codewords. This "certain number of codewords" is thus interpreted as a lower bound on optimality in terms of codewords because if you have a fewer codewords right now, you should be able to pack more while keeping the same length and minimum distance. There are better lower bounds in coding theory as well. The first few paragraphs of the introduction of the following paper may serve as a very brief summary of lower bounds on optimality of this kind:
P. Gaborit and G. Zémor, Asymptotic improvement of the Gilbert–Varshamov bound for linear codes, IEEE Trans. Inform. Theory, 54 (2008) 3865-3872
For the asymptotic case you specifically mentioned for codes, the asymptotic version of the Gilbert–Varshamov bound (which can be proved by the probabilistic method, i.e., showing that you can draw from a pool of codes an example of certain size with a positive probability) is actually quite a strong lower bound and very hard to achieve by explicit constructions.
So, given an explicit example, a quick and general way to prove its non-optimality is to try common "nonconstructive" techniques and see if you can prove the existence of a better code as a packing because they generally give stronger lower bounds. (I put the word nonconstructive in quotes because what it actually means can be vague.) Of course, the codes that nonconstructive lower bounds say exist typically do not allow for practical decoding. But good lower bounds like the Gilbert–Varshamov bound are an oft-used measure for how close your explicit example is to the hypothetical but sure-to-exist one.
As for general packing problems where it doesn't matter if it's explicit or not, your question seems to be asking if there is a method for proving that you should be able to pack more but can't prove how much. I don't know if there is such a result (although this doesn't mean much because my knowledge of packing is astonishingly poor...). But if exists, it must be proved by a genuinely nonconstructive proof. I'm interested to know if there is such a highly nonconstructive method for some packing problem, too.
