We are not ready to file our K1 package yet. I need to file a waiver based on a previous approved K1 package (approved by USA but never went through the interview or received visa); approval was April 2006.

Can I go ahead and file for a waiver now before I file our K1 package; or must I wait to file for the waiver when I send in the K1 package

Read the I-129F instructions which explains that your request for a waiver is a letter that you send with the I-129F.

http://www.uscis.gov/files/form/I-129Finstr.pdf

To request a waiver you must submit a written request with this petition accompanied by documentation of your claim to the waiver.

Yes, you have to wait. They track everything by the numbers starting with the Receipt number assigned when they send you your first notices. They could never have it connect up with your application if you sent it first. The instructions are to send it with the application.

File your waiver when you file the application. Make sure you provide much detail in your waiver including case number, dates, results of application process and final results of your process. Be business like in your explanation and provide truthful facts. If you provide full and complete explanations, then you can expect an approval.