<PAGE>
 
                                                                   EXHIBIT 10.38


                                   AGREEMENT

             AGREEMENT (the "Agreement"), dated as of January 25, 1999, by and
among Telefonos de Mexico, S.A. de C.V., a sociedad anonima organized in Mexico
with its principal place of business at Parque Via 190, Oficina 1016, Colonia
Cuauhtemoc, Mexico City, Mexico ("Telmex") and Prodigy Communications
Corporation, a Delaware corporation located at 33 South Broadway, White Plains,
New York ("Prodigy"). 

             WHEREAS, Telmex, through its Internet Directo Personal division
("IDP") offers dial up internet access throughout Mexico (the "IDP Service"),
and

             WHEREAS, Prodigy offers internet access and value added services
through the United States and has proven expertise in network and data center
operation, customer service and other services relating to the offering of
internet access to consumers; and

             WHEREAS, Telmex desires to retain Prodigy to provide certain
management and consulting services in connection with the IDP Service;

             NOW, THEREFORE, in consideration of the premises and mutual
representations, warranties, covenants and agreements contained herein and
intending to be legally bound hereby, the parties hereto agree as follows:

     1.  Services. Commencing as of the date of this Agreement, and continuing
         --------                                                             
throughout the term hereof (as described below), Prodigy shall from time to
time upon the request of Telmex provide the following services (the "Services")
 to Telmex in connection with the IDP Service:

           (a)  At Telmex's request on an as needed basis, assist in the
     negotiation of or negotiate on behalf of Telmex service level agreements
     and other agreements pertaining to the provisioning of the following
     services:

                    (i)    network/Internet Access,

                    (ii)   web hosting,

                    (iii)  customer service, including telemarkeing,
                           registration, technical support);

                    (iv)   content hosting;

                    (v)    billing;

                    (vi)   marketing and sales agreements and 

                    (vii)  data collection services.
<PAGE>
 
                                                                               2

     It is agreed and understood that the final terms and conditions of the
     agreements described above  shall remain within the discretion of Telmex.
     It is further understood and agreed that in the provision of such services,
     Telmex shall not rely on Prodigy for advice relating to legal, accounting,
     tax or finance matters.

          (b)  At Telmex's request on an as needed basis, provide ongoing advice
     and consultation in respect of customer service, administrative functions,
     and technical operations, including the following services:

               (i)   marketing the service, including advertising, packaging,
                     promotion, sales and distribution (the "Marketing");

               (ii)  Provision of Internet connection and other network
                     services;

               (iii) Content, including Internet home page;

               (iv)  Customer support, pricing and service plan, product
                     composition, billing and collection services;

               (v)   inbound telemarketing; and

               (vi)  provision of any other service that is generally provided
                     to subscribers in the Internet service provider business.

          (c)  The parties will also discuss the potential migration of certain
     functions relating to the IDP infrastructure platform, including: email,
     subscriber management and authentication systems for the IDP Subscribers to
     the Prodigy infrastructure platform and the advisability of offering a
     cobranded IDP/Prodigy Service in Mexico. Additionally, the parties will
     pursue additional opportunities, such as providing services to one another
     and joint acquisitions of subscribers.

          (d)  Prodigy may provide the Services to Telmex with its own personnel
     and resources or may contract with third parties who will be the sole
     responsibility of Prodigy, it being understood that Prodigy does not have
     the right or authority to contract with any third party in the name and in
     representation of Telmex.  Prodigy shall at all times be considered as an
     independent contractor and therefore Prodigy's personnel shall not in any
     manner be considered as Telmex's employees for purposes of applicable labor
     law.

     2.   CONSIDERATION.

          (a)  Fee.  In consideration of the services rendered by Prodigy
     hereunder, Telmex shall, during the Term of this Agreement, pay or cause to
     be paid to Prodigy on a monthly basis, the following management fee:  (i)
     with respect to IDP's first 200,000 Subscribers ("first" referring to those
     IDP Subscribers who became IDP's Subscribers first in time) ("First
     Subscribers"), 15% of the Net Subscriber Revenue attributable to such First
     Subscribers for each month, and (ii) with respect to IDP's Subscribers
     other 
<PAGE>
 
                                                                               3

     than the First Subscribers ("Other Subscribers"), 10% of the Net Subscriber
     Revenue attributable to such Other Subscribers for each month. For purposes
     of this Agreement, "Net Subscriber Revenue" shall mean, with respect to any
     period, the invoiced sales price of the IDP Service as invoiced to Telmex's
     customers after deducting the following amounts: (i) any discounts,
     promotional allowances, volume rebates or similar reductions actually
     allowed to such customers for such sales, (ii) the cost of insurance and
     freight where so invoiced to customers for such sales, (iii) any excise
     taxes imposed on such sales, and (iv) any allowances repaid or credited to
     customers due to rejected or returned orders for such sales or sales or
     included in the calculation of "Net Sales" for a prior period for which a
     fee was paid hereunder.

          The Fee shall be paid at the domicile of Prodigy or in the account
     designated by Prodigy from time to time.  All payments by Telmex and all
     other amounts payable hereunder shall be made after and with deduction for
     any present or future income, excise, stamp, or franchise taxes and any
     other taxes, fees, duties, withholdings or other charges of any nature
     whatsoever imposed by any taxing authority, including without limitation
     Mexican withholding taxes imposed with respect to Prodigy as provided for
     by the Mexican Income Tax Law (Ley del Impuesto sobre Renta) and the
     regulations thereunder.  In the event that any withholding or deduction
     from any payment to be made by Telmex hereunder is required in respect of
     any taxes pursuant to any applicable law, rule or regulation, then Telmex
     will (i) pay directly to the relevant authority the full amount required to
     be so withheld or deducted; and (ii) promptly forward to Prodigy an
     official receipt or other available documentation satisfactory to Prodigy
     evidencing such payment to such authority.

          (b)  Telmex shall render payment of the Fee due hereunder within
     fifteen (15) business days following the end of each calendar month during
     the term.  Each payment shall be accompanied by an accounting indicating
     the (i) Net Subscriber Revenue attributable to the First Subscribers and
     (ii) Net Subscriber Revenue attributable to the Other Subscribers, together
     with a calculation of the Fee due in respect thereof.

          (c)  Information.  Prodigy and Telmex shall provide each other with
               -----------                                                   
     the opportunity to audit and review, at the other party's expense, the
     books and records and other information relating to the matters covered by
     this Agreement, which books and records and other information shall be
     maintained confidentially by the other party.

3.   Term.
     ---- 

          (a)  This Agreement shall commence as of the date of execution by both
parties and, unless terminated sooner pursuant to section 3(b), shall continue
for an initial term of five (5) years, provided that Telmex may terminate this
                                       -------------                          
Agreement if it decides to suspend or substantially modify the IDP Service at
its own discretion.

          (b)  The non-defaulting party may terminate this Agreement if a
Default, as defined below, by the other party has occurred and is continuing by
giving written notice to the defaulting party.  The term "Default" shall mean
any of the following: (a) failure by a party to comply with or perform any
material provision or condition of this Agreement and, if such material breach
can 
<PAGE>
 
                                                                               4

be cured, continuance of such failure for thirty (30) days after written notice
to such party; or (b) a party becomes insolvent, is unable to pay its debts as
they mature or is the subject of a petition in bankruptcy, whether voluntary or
involuntary, or of any other proceeding under bankruptcy, insolvency or similar
laws; or makes an assignment for the benefit of creditors; or is named in, or
its property is subject to a suit for appointment of a receiver; or is dissolved
or liquidated. Additionally, Telmex shall be entitled to terminate this
Agreement on 30 days notice in the event that Prodigy sells or all substantially
all of its assets, or there is a change in control of Prodigy such that Telmex
and its affiliates (including for purposes of this Agreement Carso) fails to own
50.1% of the outstanding capital stock of Prodigy.

4.   Representations, Warranties, Indemnities.
     ---------------------------------------- 

          (a)  Each party represents and warrants to the other that: (a) it is a
     corporation duly organized, validly existing, and in good standing under
     the laws of the State of its incorporation; (b) it has all requisite
     corporate power and authority to enter into this Agreement and to carry out
     and perform its obligations under the terms of this Agreement; (c) this
     Agreement has been duly authorized and when executed and delivered will
     constitute a valid and binding obligation of such party enforceable in
     accordance with its terms, except as the same may be limited by bankruptcy,
     insolvency, moratorium, and other laws of general application affecting the
     enforcement of creditors' rights; and (d) the execution, delivery, and
     performance of and compliance with this Agreement does not and will not
     conflict with, or constitute a default under, or result in the creation of,
     any mortgage, pledge, lien, encumbrance, or charge upon any of the
     properties or assets of such party, nor result in any violation of: (i) any
     term of its certificate of incorporation or bylaws; (ii) in any material
     respect, any term or provision of any mortgage, indenture, contract,
     agreement, instrument, judgment, or decree; or (iii) to the best of its
     knowledge, any order, statute, rule, or regulation applicable to such
     party, the violation of which would have a material adverse effect on its
     business or properties.

          (b)  IN NO EVENT SHALL EITHER PARTY BE LIABLE TO THE OTHER OR TO ANY
     OTHER PERSON, INCLUDING SUBSCRIBERS, FOR INDIRECT, INCIDENTAL, OR SPECIAL
     DAMAGES, LOST PROFITS, LOST SAVINGS, OR ANY OTHER FORM OF CONSEQUENTIAL
     DAMAGES, REGARDLESS OF THE FORM OF ACTION, EVEN IF ADVISED OF THE
     POSSIBILITY OF SUCH DAMAGES, WHETHER RESULTING FROM BREACH OF ITS
     OBLIGATIONS UNDER THIS AGREEMENT OR OTHERWISE. NEITHER MAKES ANY
     WARRANTIES, AND EACH PARTY HEREBY EXPRESSLY DISCLAIMS ALL IMPLIED
     WARRANTIES, INCLUDING WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
     PARTICULAR USE OR PURPOSE. Under no circumstances shall Prodigy be liable
     to Telmex or any other Person for any loss, injury, or damage, of whatever
     kind or nature, resulting from or arising out of any mistakes, errors,
     omissions, delays, or interruptions in the receipt, transmission, or
     storage of any messages, signals or information arising out of or in
     connection with its Services or the IDP Services.
<PAGE>
 
                                                                               5

            (c)  Each party shall defend, indemnify, and hold the other harmless
   from and against any and all third party claims resulting in liabilities,
   losses, damages and costs, including reasonable attorney's fees, resulting
   from, arising out of, or in any way connected with: (i) any breach by such
   party of any warranty, representation or obligation contained herein or (ii)
   the performance of such party's duties and obligations hereunder. The
   parties' obligations under this Section shall survive the termination or
   expiration of this Agreement.

     5.  Miscellaneous.
         ------------- 

            (a)  This Agreement and the documents and agreements referred to
     herein and to be delivered pursuant hereto constitute the entire agreement
     between the parties hereto pertaining to the subject matter hereof, and
     supersede all prior and contemporaneous agreements, understandings,
     negotiations and discussions of the parties, whether oral or written
     including the Term Sheet between Prodigy and Telmex dated October 30, 1998.

            (b)  This Agreement shall be binding upon and inure to the
     benefit of and shall be enforceable by the parties hereto and their
     respective successors and permitted assigns.  This Agreement shall not be
     assigned by any party hereto without the prior written consent of the other
     parties hereto.

            (c)  All notices, requests, claims, demands and other communications
     provided for herein shall be in writing in the English language and shall
     be deemed given only if delivered to the party personally or sent to the
     party by telecopy, by registered or certified mail (return receipt
     requested) with postage and registration or certification fees thereon
     prepaid, or by any nationally recognized overnight courier, addressed to
     the party at its address set forth in the preamble to this Agreement or to
     such other address as a party may from time to time designate in writing in
     a notice given in accordance with this Section. All notices, requests,
     claims, demands and other communications given to any party hereto in
     accordance with the provisions of this Agreement shall be deemed to have
     been given on the date of receipt.

            (d)  This Agreement may be executed in one or more counterparts, and
     by the different parties hereto in separate counterparts, each of which
     when executed shall be deemed an original, but all of which taken together
     shall constitute one and the same Agreement.

            (e)  If any term, provision, clause or part of this Agreement or the
     application thereof under certain circumstances is held invalid, illegal or
     incapable of being enforced by any law or public policy, all other terms,
     provisions and parts of this Agreement shall nevertheless remain in full
     force and effect so long as the economic and legal substance of the
     transactions contemplated hereby is not affected in any manner materially
     adverse to any party.  Upon such determination that any term, provision or
     part of this Agreement is invalid, illegal or incapable of being enforced,
     the parties hereto shall negotiate in good faith to modify this Agreement
     so as to effect the original intent of the parties as closely as possible
     in an acceptable manner in order that the transactions 
<PAGE>
 
                                                                               6

     contemplated hereby are consummated as originally contemplated to the
     greatest extent possible.

           (f)  This Agreement shall be governed by and construed in accordance
     with the laws of the State of New York.

           (g)  Any party to this Agreement may (a) extend the time for the
     performance of any of the obligations or other acts of the other parties,
     (b) waive any inaccuracies in the representations and warranties of the
     other parties contained herein or in any document delivered by the other
     parties pursuant hereto or (c) waive compliance with any of the agreements
     or conditions of the other parties contained herein.  Any such extension or
     waiver shall be valid only if set forth in an instrument in writing signed
     by the party to be bound thereby.  Any waiver of any term or condition
     shall not be construed as a waiver of any subsequent breach or a subsequent
     waiver of the same term or condition, or a waiver of any other term or
     condition, of this Agreement.  The failure of any party to assert any of
     its rights hereunder shall not constitute a waiver of any such rights.

           (h)  This Agreement may not be amended, modified or supplemented
     except (a) by an instrument in writing signed by, or on behalf of, each of
     the parties hereto or (b) by a waiver in accordance with Subsection (g).
<PAGE>
 
                                                                               7

          IN WITNESS WHEREOF, the parties have executed this Agreement as of the
day and year first above written.

TELEFONOS DE MEXICO, S.A. de C.V.

By:  /s/ Adolfo Cerezo
     ---------------------------

Name:  __________________________

Title:  _________________________

PRODIGY COMMUNICATIONS CORPORATION

By:  /s/ Samer Salameh
     ----------------------------

Name:  __________________________

Title:  _________________________