As others have mentioned flexibility in destination is key. As a family of 5, we don't really look for a particular destination that we must be locked into. Using the award tickets primarily for vacations, we see what is available at what redemption rates and we go there. The world is a pretty big place.
Other points which have been mentioned but I will +1
-Diversify your award programs to include a couple alliances.
-For domestic, think Southwest. Companion Pass is great. No change fees. In the last 18 months we have booked MCO, FLL,DEN,MSY,SEA

This might be a good use for an award booking service. Sometimes it is worth it to pay

Haven't done it yet but have certainly considered it, esp when working with multiple award accounts on low availability routing to a need-to-reach destination. Just have to weigh it against the costs of simply buying the best discount tkts you can find.

I just did this last summer, 2 adults + 2 kids into CDG in mid June, return from MAD at the end of June. Booked it around the end of December 2011. The key was being flexible with my dates knowing I could leave during a specific week and being about flexible about a return date. The biggest problem I encountered was getting from FRA to CDG, not on the TATL flights. All at the lowest level pricing with US.
Now, I actually booked a non-optimal flight set, but was able to switch to my preferred flights because there were schedule changes. I did not count on the schedule changes, but it worked out great for us.
Good luck!

@farbster: I did actually hire an award service for my next summer vacation, which is not a heavily-traveled place: Vancouver and Anchorage. They are still looking for my desired dates but I do think they are having a hard time finding 4 tickets available all together in the same flight.
I have miles in many different programs so I am relatively flexible, but I would like to use a combination of them so I don't lean too heavily on United. After all, collecting miles for 4 is also a lot harder than collecting miles for 1 or 2.
I feel I have also looked into departing and arriving at different airports to include flexibility and it's still hard. But I will start looking at more regional airports, such as Philly and Boston.
I really like some of your ideas to split the party to travel with different alliances but from the same airport, but within similar departing and arriving times. I feel very comfortable traveling with one kid or both. My husband a bit less so. I think this thread gave me great tips about splitting the party, maybe 2 and 2, or 3 and 1.

@marianagiraudo - the flights may be busy due to cruises leaving from those ports...Not sure of your exact dates and if it is even in cruise season.

@marianagiraudo - have you looked at Seattle instead of Vancouver?

It it totally doable, but agree you have to be flexible at least on dates, and preferably also somewhat with location. Have a couple different places in mind and see what will work.

If you are willing to fly economy there are often many more options then if you are restricted to just biz/first.

I also completely agree that starting as soon as the schedule opens is key. Those who travel needing 1-2 seats don't often agree with that advice, but it works for me. Of course more seats may open up later, but if they are there at the beginning, grab them and don't look back.

I'm in the same situation (family of 4), and some thoughts I have come to have on the topic are to strongly consider not being locked into school holidays -- how big of a loss is it if my kids happen to miss a few days of school (especially that they are in elementary or middle school now). They may get more long term benefit of a new cultural experience than they would have sitting in class (I'll admit that I had near perfect attendance going through school -- I don't think I would have been too much worse off missing a bit more if it was to travel).

Secondly, I've started to weigh the cost/benefit of either booking some tickets at the higher level as has been suggested or even deciding to pay for a one of the tickets if needed. My strategy would be to have the paid ticket be for my spouse or me so the miles earned would be useful for future trips. While I value a free vacation as much as the next person, I've come to think its a matter of trade-offs -- do I want to wait and keep digging for the absolutely free flights for 4 or get 4 for the price of 1 and actually have a vacation planned.

Just my .02 on the topic...