AMENDED AND RESTATED EMPLOYMENT AGREEMENT

EXHIBIT 10.15

AMENDED AND RESTATED EMPLOYMENT AGREEMENT

This Amended and Restated Employment Agreement (the “Agreement”) is made as of December 30, 2003, between COMSYS Information Technology Services, Inc., a Delaware corporation (the “Company”), and Michael T. Willis (“Executive”).

The parties desire to amend and restate that certain Employment Agreement dated as of September 30, 1999, between the Company and Executive (the “Original Agreement”) and enter into this Agreement pursuant to which Executive shall be employed by the Company as the Company’s Chairman of the Board of Directors, Chief Executive Officer and President.

The parties hereto agree as follows:

1. Employment: Position and Duties. The Company agrees to employ Executive and Executive accepts such employment for the period beginning on January 1, 2004, and ending upon termination pursuant to Section 3 hereof (the “Employment Period”). During the Employment Period, Executive shall serve as the Chairman of the Board, Chief Executive Officer and President of the Company and shall have the normal duties, responsibilities and authority of the Chairman of the Board, Chief Executive Officer and President, including, without limitation, responsibility for all aspects of the daily operations of the Company and the identification, negotiation and integration of acquisitions, subject to the power of the Company’s Board of Directors (the “Board”) to expand or limit such duties, responsibilities and authority and to override actions of the Chairman, Chief Executive Officer and President.

2. Salary, Bonus and Benefits. During the Employment Period, the Company will pay Executive a base salary (the “Annual Base Salary”) as the Compensation Committee of the Board (the “Compensation Committee”) may designate from time to time, at the rate of not less than $425,000 per annum, which amount shall be reviewed annually and shall be subject to an annual increase as determined by the Compensation Committee in its sole discretion. Executive’s Annual Base Salary for any partial year will be prorated based upon the number of days elapsed in such year. Executive will be eligible to receive an annual bonus (a “Bonus”) commencing with the fiscal year ending December 31, 2004, based upon the Company’s achievement of EBITDA targets prepared by the CEO and CFO in connection with the annual budget and approved by the Compensation Committee (the “EBITDA Target”). The annual bonus target will initially be equal to $250,000 (the “Bonus Target”) and shall be subject to an annual increase as determined by the Compensation Committee.

Executive’s Bonus will be equal to:

40% of the Bonus Target if the Company achieves 90% of the EBITDA Target;

60% of the Bonus Target if the Company achieves 95% of the EBITDA Target;

100% of the Bonus Target if the Company achieves 100% of the EBITDA Target;

120% of the Bonus Target if the Company achieves 105% of the EBITDA Target;

160% of the Bonus Target if the Company achieves 110% of the EBITDA Target; and

200% of the Bonus Target if the Company achieves 120% of the EBITDA Target.

The Company must attain the respective EBITDA Target threshold before the percentage of the Bonus Target increases. There will be no pro-ration of the amount of the Bonus between the targeted achievement levels. The Bonus shall be due and payable to Executive prior to March 15 of the following year; provided however, in the event the audit of the financials have not been completed and such audit will affect the determination of the Bonus, then the Company and Executive may mutually agree to postpone the payment date of the Bonus. During the Employment Period, Executive shall continue to be entitled to such perquisites and reimbursements as Executive currently receives and any additional perquisites as may be customary for executives or as may be agreed to by Executive and the Compensation Committee, including reimbursement of Executive’s costs for benefit plans. The Executive will continue to participate in and be eligible for any plan established by the Company to provide benefits to its employees or any executive at the time Executive meets the eligibility criteria established for each plan. Reimbursement payments will be made to Executive not later than 30 days after Executive’s presentation to the Company of documentation detailing such expenses in form reasonably satisfactory to the Company.

3. Term; Separation and Additional Payments.

(a) Term: Separation. The term of the Employment Period shall commence on January 1, 2004 and continue to December 31, 2006 (the “Original Term”) and renew automatically for successive one-year terms (each, a “Renewal Term”) unless notice of non-renewal is given by either party to the other party at least six months prior to the end of the Original Term or any Renewal Term (the “Expiration Date”); provided that the Employment Period may also be terminated prior to such Expiration Date (i) by Executive for any reason, (ii) by the Company with Cause or (iii) by the Company without Cause. In the event that (i) the Company does not renew the Agreement at the end of the Original Term or any Renewal Term, (ii) the Company terminates the Employment Period prior to the Expiration Date without Cause or (iii) Executive terminates the Employment Period prior to the Expiration Date for Good Reason, Executive shall be entitled to receive an amount equal to (A) two times Executive’s Annual Base Salary as of the date of such termination (the “Severance Amount”), divided by (B) twenty-four (24), payable each month during the two year period following termination, in exchange for Executive signing a release of claims against the Company; provided, however, that all of Executive’s future rights to perquisites, benefits, bonuses and reimbursements provided for in this Agreement shall cease immediately upon the termination of the Employment Period, except that, during the 12 month period following the date of such termination of the Employment Period, the Company shall maintain in full force and effect for the continued benefit of Executive all benefits available to Executive under all medical plans and programs of the Company provided to him by the Company immediately prior to termination of the Employment Period and reimburse Executive for all costs associated with electing COBRA benefits for such benefit plans during the 12 month period. In the event Executive is terminated without Cause in connection with a sale or merger of the Company in which the enterprise value of the Company is valued at less than $132 million as determined by the Compensation Committee, Executive shall receive a Severance Amount equal to Executive’s Annual Base Salary, plus all benefits described above, rather than two times Executive’s Annual Base Salary.

2

The Compensation Committee may also elect to pay the Severance Amount in the form of a lump sum payment rather than monthly payments.

(b) Certain Additional Payments by the Company. Anything in this Agreement to the contrary notwithstanding, in the event it shall be determined that any payment or distribution by the Company or any other person to or for the benefit of Executive, whether paid or payable or distributed or distributable pursuant to the terms of this Agreement or otherwise (a “Payment”), would be subject to the excise tax imposed by Section 4999 of the Internal Revenue Code of 1986, as amended, or any interest or penalties with respect to such excise tax (such excise tax, together with any such interest and penalties, are hereinafter collectively referred to as the “Excise Tax”), then Executive shall be entitled to receive promptly from the Company an additional payment (a “Gross-Up Payment”) in an amount such that after payment by Executive of all taxes (including any interest or penalties imposed with respect to such taxes), including any Excise Tax, imposed upon the Gross-Up Payment, Executive retains an amount of the Gross-Up Payment equal to the Excise Tax imposed upon the Payments.

4. Definitions.

“Cause” shall mean (A) Executive being determined by a unanimous vote of the Board, excluding Executive, to have refused to perform the duties assigned to Executive under this Agreement and not to have remedied the situation within a reasonable period of time after receipt of written notice from the Company specifying the refusal; (B) Executive having been determined by a unanimous vote by the Board, excluding Executive, to have refused to abide by the Company’s written policies, rules, procedures or directives furnished to him and not to have remedied the situation within a reasonable period of time after receipt of written notice from the Company specifying the refusal; (C) Executive’s gross negligence, reckless or willful misconduct with respect to the Company or any of its Subsidiaries which damages such entity’s relationship with its customers, suppliers or employees in a manner which has a material adverse effect on the Company and its Subsidiaries on a combined basis; or (D) Executive having been determined by a unanimous vote of the Board, excluding Executive, to be guilty of fraud, dishonesty or a crime involving moral turpitude.

“Good Reason” means any of the following: (A) a reduction in Executive’s compensation or employment benefits, (B) an adverse change in Executive’s title, (C) a material adverse change in Executive’s responsibilities, duties, or authority, (D) a requirement that Executive move his residence or report to work more than 75 miles from the principal executive offices of the Company as of the date of this Agreement, or (E) a material breach of this Agreement by the Company that is not remedied by the Company within 30 days of the Company’s receipt of written notice of such breach from Executive.

“Subsidiary” means any corporation, limited partnership, limited liability company or other entity of which the Company owns securities having a majority of the ordinary voting power in electing the board of directors directly or through one or more subsidiaries.

5. Confidential Information. Executive acknowledges that the information, observations and data obtained by him during the course of his performance under this Agreement concerning the business and affairs of the Company and its affiliates are the property

3

of the Company. Therefore, Executive agrees that he will not disclose to any unauthorized person or use for his own account any of such information, observations or data without the Board’ s written consent, unless and to the extent that the aforementioned matters become generally known to and available for use by the public other than as a result of Executive’s wrongful acts or omissions to act. Executive agrees to deliver to the Company at the termination of his employment, or at any other time the Board may request in writing, all memoranda, notes, plans, records, reports and other documents (and copies thereof) relating to the business of the Company and its affiliates (including, without limitation, all acquisition prospects, lists and contact information) which he may then possess or have under his control.

6. Noncompetition and Nonsolicitation

(a) Noncompetition. Executive acknowledges that in the course of his employment with the Company he will become familiar with the Company’s trade secrets and with other confidential information concerning the Company and that his services will be of special, unique and extraordinary value to the Company. Therefore, Executive agrees that, during the Employment Period and for the lesser of (i) two years after the termination of the Employment Period or (ii) such time as the Company notifies Executive in writing of the termination of the restrictions set forth in this Section 6 (the “Noncompete Period”), he shall not directly or indirectly own, manage, control, participate in, consult with, render services for, or in any manner engage in any business competing with the core businesses of the Company as such businesses exist or are in process on the date of the termination of Executive’s employment, within the geographical area in which the Company or its Subsidiaries engage in such business; provided, however, that the foregoing restriction shall not apply at any time if Executive’s employment is terminated by Executive for Good Reason or by the Company for any reason other than Cause. For purposes of this Section 6, “core business” shall mean any business from which the Company derives in excess of 20% of the Company’s annual revenues.

(b) Nonsolicitation. During the Noncompete Period, Executive shall not directly or indirectly through another entity (i) induce or attempt to induce any employee of the Company or any Subsidiary to leave the employ of the Company or such Subsidiary, or in any way interfere with the relationship between the Company or any Subsidiary and any employee thereof, (ii) hire any person who was an employee of the Company or any Subsidiary at any time during the Employment Period (other than an employee whose employment is terminated by the Company), or (iii) induce or attempt to induce any customer, supplier, licensee or other business relation of the Company or any Subsidiary to cease doing business with the Company or such Subsidiary, or in any way interfere with the relationship between any such customer, supplier, licensee or business relation and the Company or any Subsidiary.

(c) Enforcement. If, at the time of enforcement of Section 5 or Section 6 of this Agreement, a court holds that the restrictions stated herein are unreasonable under circumstances then existing, the parties hereto agree that the maximum duration, scope or geographical area reasonable under such circumstances shall be substituted for the stated period, scope or area and that the court shall be allowed to revise the restrictions contained herein to cover the maximum duration, scope and area permitted by law. Because Executive’s services are unique and because Executive has access to confidential information, the parties hereto agree that money damages would be an inadequate remedy for any breach of this Agreement. Therefore, in the event of a

4

breach or threatened breach of this Agreement, the Company or its successors or assigns may, in addition to other rights and remedies existing in their favor, apply to any court of competent jurisdiction for specific performance and/or injunctive or other relief in order to enforce, or prevent any violations of, the provisions hereof.

7. Notices. Any notice provided for in this Agreement must be in writing and must be either personally delivered, mailed by first class mail (postage prepaid and return receipt requested) or sent by reputable overnight courier service (charges prepaid) to the recipient at the address below indicated:

If to the Company:

COMSYS Information Technology Services, Inc.

4400 Post Oak Parkway, Suite 1800

Houston, TX 77027

Attention: Margaret G. Reed, General Counsel

If to Executive:

Michael T. Willis

4400 Post Oak Parkway, Suite 1800

Houston, TX 77027

with a copy to:

Michael T. Willis

3825 Piping Rock

Houston, TX 77027

or such other address or to the attention of such other person as the recipient party shall have specified by prior written notice to the sending party. Any notice under this Agreement will be deemed to have been given when so delivered or sent or, if mailed, five days after deposit in the U.S. mail.

8. Indemnification. The Company shall indemnify, defend and hold harmless Executive from and against and in respect of any and all losses, damages, liabilities, costs and expenses, including reasonable attorney’s fees, suffered or incurred by Executive by reason of, or arising out of:

(a) acts or omissions of Executive in connection with his service as an officer or director of PSINet Consulting Solutions Holdings, Inc. (formerly Metamor Worldwide, Inc.), if PSINet Consulting Solutions Holdings, Inc. does not indemnify Executive for such loss, damage, liability, cost and expense; or

(b) any claims, liabilities, obligations, damages, costs and expenses, known or unknown, fixed or contingent, against Executive which arise out of or result from (i) the sale of

5

the Company by PSINet Consulting Solutions, Inc. or (ii) any transaction or agreement related thereto or in contemplation thereof; provided, however, that Executive shall not receive any indemnification under this Section 8 for acts or omissions which constitute gross negligence or willful misconduct by Executive.

9. General Provisions.

(a) 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 provision of this Agreement is held to be invalid, illegal or unenforceable in any respect under any applicable law or rule in any jurisdiction, such invalidity, illegality or unenforceability will not affect any other provision or any other jurisdiction, but this Agreement will be reformed, construed and enforced in such jurisdiction as if such invalid, illegal or unenforceable provision had never been contained herein.

(b) Complete Agreement. This Agreement, those documents expressly referred to herein, the registration rights agreement and stockholders agreement referenced in Section 1(h) of Executive’s Senior Management Agreement with the Company, and other documents of even date herewith embody the complete agreement and understanding among the parties and supersede and preempt any prior understandings, agreements or representations by or among the parties, written or oral, which may have related to the subject matter hereof in any way.

(c) Counterparts. This Agreement may be executed in separate counterparts, each of which is deemed to be an original and all of which taken together constitute one and the same agreement.

(d) Successors and Assigns. Except as otherwise provided herein, this Agreement shall bind and inure to the benefit of and be enforceable by Executive, the Company and their respective successors and assigns; provided that the rights and obligations of Executive under this Agreement shall not be assignable.

(e) Choice of Law. The corporate law of the State of Delaware will govern all questions concerning the relative rights of the Company and its stockholders. All other questions concerning the construction, validity and interpretation of this Agreement and the exhibits hereto will be governed by and construed in accordance with the internal laws of the State of Texas, without giving effect to any choice of law or conflict of law provision or rule (whether of the State of Texas or any other jurisdiction) that would cause the application of the laws of any jurisdiction other than the State of Texas.

(f) Remedies. Each of the parties to this Agreement will be entitled to enforce its rights under this Agreement specifically, to recover damages and costs (including attorneys’ fees) caused by any breach of any provision of this Agreement and to exercise all other rights existing in its favor. The parties hereto agree and acknowledge that money damages may not be an adequate remedy for any breach of the provisions of this Agreement and that any party may in its sole discretion apply to any court of law or equity of competent jurisdiction for specific performance and/or other injunctive relief in order to enforce or prevent any violations of the provisions of this Agreement.

6

(g) Amendment and Waiver. The provisions of this Agreement may be amended and waived only with the prior written consent of the Company and Executive.

* * * * * *

IN WITNESS WHEREOF, the parties hereto have executed this Agreement as of the date first written above.

7