Solver-related comments below are specific to CPLEX but may apply to some other solvers.
First comment: Out of memory errors can be postponed (by tweaking the parameter settings for swapping stuff out to disk) or possibly eliminated (by switching to depth-first search). Neither guarantees the optimum will be found within your lifetime.
Second comment: If you have not already done so, you might try switching the MIP emphasis from its default setting to the setting that stressed tightening the best bound. In addition, there are a variety of settings that can be tweaked to increase the use of various cuts (which may or may not help), or to use strong branching (which may or may not help). Switching emphasis changes some of those for you (I think), but I couldn't say which ones.
Third comment: You might want to look at an excellent paper by Klotz and Newman titled "Practical Guidelines for Solving Difficult Mixed Integer Linear Programs" (Surveys in Operations Research and Management Science, 2013, 18, 18-32). There's a proof (PDF) on Alexandra Newman's web site.
Fourth comment: Some formulations are known to be weak. A classic example is a "big M" model with a, well, big "M". If you can tighten your formulation, that should be your first choice. Unfortunately, tighter formulations are not always easy to find.