CONSULTING AGREEMENT

Exhibit 10.16

CONSULTING AGREEMENT

THIS CONSULTING AGREEMENT (this “Agreement”) is made and entered into as of January 3, 2007 (the “Effective Date”), by and between Welsh, Carson, Anderson & Stowe IX, L.P., a Delaware limited partnership (“WCAS”), and Local Insight Media, Inc., a Delaware corporation (the “Consultant”).

RECITALS:

WHEREAS, WCAS is a party to that certain Share Exchange Agreement dated as of December 12, 2006 (the “Share Exchange Agreement”), by and among WIN, the Parents and the WCAS Subs (as those terms are defined in the Share Exchange Agreement);

WHEREAS, WCAS is an Affiliate (as that term is defined below) of: (i) the WCAS Subs and (ii) Consultant;

WHEREAS, pursuant to the Share Exchange Agreement, the WCAS Subs will receive shares of common stock of Windstream Regatta Holdings, Inc. (“Holdings”), which at or prior to the Closing (as that term is defined in the Share Exchange Agreement) will own all the issued and outstanding capital stock of Windstream Yellow Pages, Inc.; and

WHEREAS, WCAS desires to engage Consultant to perform certain consulting services relating to the WCAS Subs’ acquisition, ownership and operation of Holdings and its subsidiaries, and Consultant desires to provide such consulting services, all in accordance with the terms of this Agreement;

NOW, THEREFORE, in consideration of the foregoing premises and the respective agreements hereinafter set forth and the mutual benefits to be derived herefrom, Consultant and WCAS hereby agree as follows:

1. Definitions. As used herein, the following terms shall have the following respective meanings:

“Affiliate” means, with respect to any Person, any other Person that, directly or indirectly through one or more of its intermediaries, controls, is controlled by or is under common control with such Person.

“Services” has the meaning set forth in Section 2.

“Person” means an individual, a partnership, a corporation, an association, a limited liability company, a joint stock company, a trust, a joint venture, an unincorporated organization or any other entity (including any governmental entity or any department, agency or political subdivision thereof).

2. Engagement of Consultant; Scope of Services. WCAS hereby engages Consultant as an independent consultant to provide such consulting services (including strategic, operational,

finance and accounting, treasury, legal, human resource, integration and/or administrative services) relating to the WCAS Subs’ acquisition, ownership and operation of Holdings and its subsidiaries as WCAS may from time to time request (the “Services”), and Consultant hereby accepts such engagement.

3. Compensation.

(a) In consideration of Consultant’s provision of the Services, WCAS shall cause Holdings (or one or more of its subsidiaries or Affiliates) to pay to Consultant an amount equal to one hundred fifteen percent (115%) of Consultant’s fully burdened cost (including all direct costs and allocable indirect costs) of providing the Services. Such compensation shall be paid as follows:

(i) At or following the Closing, Consultant shall deliver to WCAS an invoice that: (A) describes in reasonable detail the Services rendered during the period commencing on the Effective Date and ending at the Closing and (B) sets forth one hundred fifteen percent (115%) of the fully burdened cost of such Services. Subject to WCAS’s approval of the nature and cost of such Services, WCAS shall cause Holdings (or one or more of its subsidiaries or Affiliates) to pay such invoice as promptly as practicable following the Closing (and in any event within thirty (30) days following the date of such invoice).

(ii) Within fifteen (15) days after the end of each calendar quarter following the Closing, Consultant shall deliver to WCAS an invoice that: (A) describes in reasonable detail the Services rendered during the preceding calendar quarter (or, for the first calendar quarter ending following the Closing, during the period commencing on the day after the Closing and ending on the last day of such calendar quarter) and (B) sets forth one hundred fifteen percent (115%) of the fully burdened cost of such Services. Subject to WCAS’s approval of the nature and cost of the Services described in each such invoice, WCAS shall cause Holdings (or one or more of its subsidiaries or Affiliates) to pay such invoice thirty (30) days following the date thereof.

(b) In addition to the amounts payable pursuant to Section 3(a), WCAS agrees to cause Holdings (or one or more of its subsidiaries or Affiliates) to reimburse Consultant for all reasonable expenses incurred by Consultant that are directly attributable to the Services. Consultant will invoice WCAS for any such reimbursable expenses, and each such invoice shall be accompanied by an itemized account of the claimed reimbursable expenses, together with copies of receipts relating thereto. Notwithstanding the foregoing, Consultant shall not be entitled to invoice WCAS for any reimbursable expenses prior to the Closing. WCAS shall cause Holdings (or one or more of its subsidiaries or Affiliates) to pay the amounts set forth in each such invoice within thirty (30) days following the date thereof.

4. Independent Contractor. Nothing herein shall be construed to create a joint venture or partnership between the parties hereto or an employee/employer relationship between WCAS or any of its Affiliates and Consultant’s personnel. Consultant shall be an independent contractor pursuant to this Agreement. Neither party hereto shall have any express or implied right or authority to assume

-2-

or create any obligations on behalf of or in the name of the other party or to bind the other party to any contract, agreement or undertaking with any third party.

5. Liability. Neither Consultant nor any of its Affiliates, stockholders, employees, consultants or agents shall be liable to WCAS for any loss, liability, damage or expense arising out of or in connection with the performance of the Services, unless such loss, liability, damage or expense is caused by the gross negligence, willful misconduct or bad faith of Consultant or its Affiliates, stockholders, employees, consultants or agents.

6. Term.

(a) Unless sooner terminated as provided in Section 6(b), this Agreement shall commence on the Effective Date and shall continue in full force and effect until December 31, 2007, and shall thereafter automatically renew for successive one (1) year terms, unless, not less than thirty (30) days prior to the expiration of the then-current term of this Agreement, either party notifies the other party in writing of its decision to terminate this Agreement upon the expiration of the then-current term of this Agreement.

(b) This Agreement may be terminated:

(i) By Consultant or WCAS, immediately upon written notice of termination, in the event of a material breach of this Agreement by the other party, if such breach continues uncured for a period of twenty (20) days after written notice of such breach;

(ii) Automatically and without notice: (A) upon the institution by or against either party of insolvency, receivership or bankruptcy proceedings; (B) upon either party’s making of an assignment for the benefit of creditors; or (C) upon either party’s dissolution or ceasing to do business; or

(iii) By an executed written agreement between Consultant and WCAS.

7. Notices. All notices, demands or other communications to be given or delivered by reason of the provisions of this Agreement will be in writing and will be deemed to have been given: (i) on the date of personal delivery to the recipient or an officer of the recipient; or (ii) when sent by telecopy or facsimile machine to the number shown below on the date of such confirmed facsimile or telecopy transmission (provided that a confirming copy is sent via overnight mail); or (iii) when properly deposited for delivery by a nationally recognized commercial overnight delivery service, prepaid, or by deposit in the United States mail, certified or registered mail, postage prepaid, return receipt requested. Such notices, demands and other communications will be sent to each party at the address indicated for such party below:

-3-

If to Consultant:

Local Insight Media, Inc.

8310 South Valley Highway, Third Floor

Englewood, Colorado 80112

Attention: John S. Fischer, Esq.

Facsimile: 303 ###-###-####

If to WCAS:

Welsh, Carson, Anderson & Stowe IX, L.P.

320 Park Avenue, Suite 2500

New York, New York 10022

Attention: John Almeida, Jr.

Facsimile: 212 ###-###-####

8. Entire Agreement; Modification. This Agreement: (i) contains the complete and entire understanding and agreement of Consultant and WCAS with respect to the subject matter hereof and (ii) supersedes all prior and contemporaneous understandings, conditions and agreements, oral or written, express or implied, regarding the engagement of Consultant in connection with the subject matter hereof. The provisions of this Agreement may be amended, modified and/or waived only by a written instrument executed by Consultant and WCAS.

9. Waiver of Breach. The waiver by either party of a breach of any provision of this Agreement by the other party shall not operate or be construed as a waiver of any subsequent breach of that provision or any other provision hereof.

10. Assignment; Successors and Assigns. Neither party hereto may assign this Agreement or any interest herein without the prior written consent of the other party hereto; provided, however, that: (i) no such prior written consent shall be required for Consultant to assign this Agreement and its rights and obligations hereunder to (A) any Affiliate of Consultant or (B) any Person that acquires all or substantially all the assets or shares of capital stock of Consultant and (ii) either party to assign this Agreement and its rights and obligations hereunder to its lenders for collateral security purposes. All covenants and agreements contained in this Agreement by or on behalf of any of the parties hereto will bind and inure to the benefit of the respective successors and assigns of the parties hereto whether so expressed or not.

11. Counterparts. This Agreement may be executed and delivered by each party hereto in separate counterparts (including by means of facsimile), each of which when so executed and delivered shall be deemed an original and both of which taken together shall constitute one and the same agreement.

12. Severability. Whenever possible, each provision of this Agreement will be interpreted in such manner as to be effective and valid under applicable law, but if any one or more of the

-4-

provisions of this Agreement is held to be invalid, illegal or unenforceable in any respect, such invalidity, illegality or unenforceability shall not affect any other provision of this Agreement. Moreover, if one or more of the provisions contained in this Agreement shall for any reason be held to be excessively broad or unreasonable as to the scope, duration, area, activity or substituted by the appropriate judicial body so as to cover the maximum scope, duration, area or activity or subject permitted by applicable law.

13. Governing Law. Issues and questions concerning the construction, validity, enforcement and interpretation of this Agreement will be governed by, and construed in accordance with, the laws of the State of Delaware, without giving effect to any choice of law or conflict of law rules or provisions (whether of the State of Delaware or any other jurisdiction) that would cause the application of the laws of any jurisdiction other than the State of Delaware. In furtherance of the foregoing, the internal law of the State of Delaware will control the interpretation and construction of this Agreement.

14. WAIVER OF JURY TRIAL. EACH PARTY TO THIS AGREEMENT HEREBY WAIVES, TO THE FULLEST EXTENT PERMITTED BY LAW, ANY RIGHT TO TRIAL BY JURY OF ANY CLAIM, DEMAND, ACTION, OR CAUSE OF ACTION (I) ARISING UNDER THIS AGREEMENT OR (II) IN ANY WAY CONNECTED WITH OR RELATED OR INCIDENTAL TO THE DEALINGS OF THE PARTIES HERETO IN RESPECT OF THIS AGREEMENT OR ANY OF THE TRANSACTIONS RELATED HERETO, IN EACH CASE WHETHER NOW EXISTING OR HEREAFTER ARISING, AND WHETHER IN CONTRACT, TORT, EQUITY, OR OTHERWISE. EACH PARTY TO THIS AGREEMENT HEREBY AGREES AND CONSENTS THAT ANY SUCH CLAIM, DEMAND, ACTION, OR CAUSE OF ACTION WILL BE DECIDED BY COURT TRIAL WITHOUT A JURY AND THAT THE PARTIES TO THIS AGREEMENT MAY FILE AN ORIGINAL COUNTERPART OR A COPY OF THIS AGREEMENT WITH ANY COURT AS WRITTEN EVIDENCE OF THE CONSENT OF THE PARTIES HERETO TO THE WAIVER OF THEIR RIGHT TO TRIAL BY JURY.

15. No Strict Construction. The parties hereto have participated jointly in the negotiation and drafting of this Agreement. In the event any ambiguity or question of intent or interpretation arises, this Agreement shall be construed as if drafted jointly by the parties hereto, and no presumption or burden of proof shall arise favoring or disfavoring any party by virtue of the authorship of any of the provisions of this Agreement.

16. Descriptive Headings; Interpretation. The descriptive headings of this Agreement are inserted for convenience only and do not constitute a substantive part of this Agreement. Whenever required by the context, any pronoun used in this Agreement shall include the corresponding masculine, feminine, or neuter forms, and the singular form of nouns, pronouns, and verbs shall include the plural and vice versa. The use of the word “including” in this Agreement shall be, in each case, by way of example and without limitation. The use of the words “or,” “either,” and “any” shall not be exclusive. Reference to any agreement, document, or instrument means such agreement, document, or instrument as amended or otherwise modified from time to time in accordance with the terms thereof, and, if applicable, hereof.

-5-

17. Survival. The respective rights and obligations of the parties under Sections 3, 4, 5, 7, 8, 12, 13, 14, 15, 16 and 17 of this Agreement shall survive the termination or expiration of this Agreement.

[Signature page follows]

*  *  *  *  *  *  *

-6-

IN WITNESS WHEREOF, the undersigned have executed this Agreement as of the Effective Date.

-7-