Dealing with duplicates in Genetic Algorithm
What you've hit upon is the basic mechanism that drives GAs -- convergence to some fixed point that you hope is near optimal. In your case, clearly it isn't. So the name of the game is to try and balance this tendency to drive convergence with the competing interest of exploring the space looking for other solutions. There's no silver bullet for this problem -- you always end up tuning things to suit your particular problem.

In general, there are two ways to do this. One is to delay convergence for longer, thus giving the algorithm more time to find better solutions. You can switch to a weaker selection operator (binary tournament selection for example), you can increase your mutation rate, etc. The other option is to allow the algorithm to converge, but figure out a sensible way to restart the search (as you mentioned, putting random points in tends not to work because their fitness is too low to allow them to survive and contribute to the search).

I'll give an example of the latter approach. There is a relatively-little known algorithm called CHC (Eshelman 1991) that tends to work really well for a lot of problems. Unfortunately, one reason it's little-known is that the only way to access the original paper is to buy the printed proceedings of the first FOGA conference, but you can probably find a little bit of information online, hopefully enough to get you started. I can give you something of a quick overview though. In rough pseudocode, CHC looks like

delta = k/4               # k = chromosome length
while not done
    create new child population
    for i = 1 to n/2     # n = population size
        select p1, p2 from population without replacement
        if hamming_distance(p1, p2) &gt; delta
            c1, c2 = HUX crossover(p1, p2)
            insert c1, c2 into child pop
        end if
    end for
    if child pop is empty
        delta = delta - 1
    else
        take best n individuals from union of parent and child populations as next population
    end if
    if delta &lt; 0
        keep one copy of best individual in population
        generate n-1 new population members by flipping 35% of the bits of the best individual
        delta = k/4
    end if


The HUX crossover operator is like uniform crossover, but instead of choosing randomly between the parents independently for each bit, it exchanges precisely half the differing bits from the parents. 

You then just keep running this loop until you decide to quit, either because you've found a good enough solution, you've exhausted the amount of time you have to spend on the problem, or whatever other criteria you desire.