How to solve the feasibility problem in 0-1 integer programs?
The fundamental misconception seems to be: you seem to expect there to be some good way to solve NP-hard problems.  But the whole point of NP-hard problems is that there is (most likely) no good, general way to find optimal solutions to NP-hard problems in a reasonable amount of time.  So, you seem to be asking for something that (most likely) doesn't exist.

To answer your specific questions:


  [Here's an example where the grey first-fit algorithm doesn't find the optimal solution to a bin-packing problem.]  How to solve this issue with the greedy first-fit algorithm?


You can't.  The greedy first-fit algorithm isn't guaranteed to find an optimal solution (and often won't).  Morever, as you said, it's NP-hard even to find a feasible solution -- therefore, you shouldn't expect the greedy first-fit algorithm to be guaranteed to find a feasible solution, either.  It's no surprise that it fails to find a feasible solution to a NP-hard problem.  And there is (most likely) no way to fix it, while still having an efficient running time.


  In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors?


In general, there may be no way.


  Any suggestions where to find solutions to feasibility of 0-1 integer programs?


There's lots of literature on methods for solving integer linear programming (ILP).  None of them are guaranteed to find feasible solutions within a polynomial running time (after all, the problem of finding a feasible solution is NP-hard), though some of them might work well enough on some problems that you run into in practice.  Rather than study the literature and try to implement the known methods, you're probably better off using an off-the-shelf ILP solver -- the developers who implemented the ILP solver did that for you.