<PAGE>

                                                                     EXHIBIT 4.6

                        REGISTRATION  RIGHTS AGREEMENT

     This REGISTRATION RIGHTS AGREEMENT (this "Agreement"), dated as of April
                                               ---------
28, 2000, by and between CAIS Internet, Inc., a Delaware corporation (the

"Company"), and Microsoft Corporation, a Washington corporation (the "Holder").
--------                                                              ------

                             W I T N E S S E T H:
                             - - - - - - - - - -

     WHEREAS, the Company and the Holder have entered into a certain Series F
Convertible Participating Preferred Stock Purchase Agreement of even date
herewith (the "Purchase Agreement"), pursuant to which the Company will sell to
               ------------------
the Holder, and the Holder will purchase from the Company, 40,000 shares of the
Company's Series F Preferred Stock, par value $.01 per share (the "Shares");
                                                                   ------

     WHEREAS, the Company has issued to the Holder a certain Common Stock
Warrants of even date herewith (the "Warrants") that entitle the Holder to
                                     --------
purchase from the Company up to 1,500,000 shares of Common Stock, par value $.01
per share, of the Company (the "Warrant Shares"); and
                                --------------

     WHEREAS, the execution and delivery of this Agreement is a condition
precedent to the consummation of the purchase of the Shares pursuant to the
Purchase Agreement (the "Purchase").
                         --------

     NOW, THEREFORE, in consideration of the foregoing and of the mutual
covenants and agreements set forth herein, and other good and valuable
consideration, the receipt and sufficiency of which are hereby acknowledged, the
parties hereto agree as follows:

     1.   Definitions.
          -----------

          As used in this Agreement, the following capitalized defined terms
shall have the following meanings:

          "CAIS Prospectus" shall have the meaning set forth in Section 7(d)
           ---------------
hereof.

          "CAIS SEC Reports" shall have the meaning set forth in Section 7(d)
           ----------------
hereof.

          "Common Stock" shall mean the Common Stock, par value $.01 per share,
           ------------
of the Company.

          "Company" shall have the meaning set forth in the preamble and also
           -------
shall include the Company's successors.

          "Demand Period" shall have the meaning set forth in Section 3.
           -------------

          "Demand Registration" shall have the meaning set forth in Section 3.
           -------------------
<PAGE>

          "Demand Registration Request" shall have the meaning set forth in
           ---------------------------
Section 3.

          "Exchange Act" shall mean the Securities Exchange Act of 1934, as
           ------------
amended from time to time.

          "Fair Market Value" means, per share of Common Stock, (i) if the
           -----------------
Common Stock is traded on a national securities exchange or system, or is
actively traded over-the-counter, the average of the closing sales prices for
the Common Stock on such exchange or system or format for the two (2) trading
days preceding, but not including, the date of a Demand Registration Request, or
(ii) if the Common Stock is not so traded, the fair market value as determined
in the discretion of the Board of Directors of the Company.

          "Form S-1" means such form under the Securities Act as in effect on
           --------
the date hereof or any registration form under the Securities Act subsequently
adopted by the SEC which permits inclusion or incorporation of substantial
information by reference to other documents filed by the Company with the SEC.

          "Holder" shall have the meaning set forth in the preamble.
           ------

          "Purchase" shall have the meaning set forth in the preamble.
           --------

          "Offering" shall mean the sale of Registrable Securities in connection
           --------
with any public offering.

          "Other Holder" shall have the meaning set forth in Section 5(c)
           ------------
hereof.

          "Person" shall mean an individual, partnership, limited liability
           ------
company, corporation, trust, unincorporated organization or other entity, or a
government or agency or political subdivision thereof.

          "Piggyback Notice" shall have the meaning set forth in Section 5(a)
           ----------------
hereof.

          "Piggyback Registration" shall have the meaning set forth in Section
           ----------------------
5(a) hereof.

          "Prospectus" shall mean the prospectus included in a Registration
           ----------
Statement for the registration with the SEC of all or a portion of the
Registrable Securities, including any preliminary prospectus, and any such
prospectus as amended or supplemented by any prospectus supplement and by all
other amendments and supplements to such prospectus, including post-effective
amendments, and in each case including all material incorporated by reference
therein.

          "Registrable Securities" shall mean any shares of Common Stock issued
           ----------------------
or issuable upon (i) the conversion of the Holder's Shares in accordance with
the Company's Amended and Restated Certificate of Incorporation, as amended, and
the

                                       2
<PAGE>

Certificate of Designation relating to the Shares, and (ii) the Warrant Shares,
but excluding, in each case, (x) Registrable Securities for which a Registration
Statement relating to the sale thereof shall have become effective under the
Securities Act or (y) Registrable Securities which the holder thereof may sell
in any one three-month period pursuant to Rule 144 under the Securities Act (or
such successor rule as may be adopted).

          "Registration Expenses" shall mean any and all expenses incident to
           ---------------------
performance of or compliance with the registration rights granted under Section
3,  Section 4 or Section 5 of this Agreement, including, without limitation:
(i) all SEC, stock exchange or National Association of Securities Dealers, Inc.
(the "NASD") registration and filing fees, (ii) all fees and expenses incurred
      ----
in connection with compliance with state securities or blue sky laws (including
reasonable fees and disbursements of counsel in connection with blue sky
qualification of any of the Registrable Securities and the preparation of a blue
sky memorandum) and compliance with the rules of the NASD, (iii) all expenses of
any Persons in preparing or assisting in preparing, word processing, printing
and distributing any Registration Statement, any Prospectus, certificates and
other documents relating to the performance of and compliance with this
Agreement, (iv) all fees and expenses incurred in connection with the listing,
if any, of any of the Registrable Securities on any securities exchange or
exchanges pursuant to Section 6(1) hereof, and (v) the fees and disbursements of
counsel for the Company and of the independent public accountants of the
Company, including the expenses of any special audits or "cold comfort" letters
required by or incident to such performance and compliance.  Registration
Expenses shall specifically exclude underwriting discounts and commissions, the
fees and disbursements of counsel representing the Holder and transfer taxes, if
any, relating to the sale or disposition of Registrable Securities by the
Holder, all of which shall be borne by the Holder in all cases.

          "Registration Statement" shall mean a registration statement of the
           ----------------------
Company and any other entity required to be a registrant with respect to such
registration statement pursuant to the requirements of the Securities Act which
covers some or all of the Registrable Securities, and all amendments and
supplements to such registration statement, including post-effective amendments,
in each case including the Prospectus contained therein, all exhibits thereto
and all materials incorporated by reference therein.

          "SEC" shall mean the Securities and Exchange Commission.
           ---

          "Securities Act" shall mean the Securities Act of 1933, as amended
           --------------
from time to time.

          "Shares" shall have the meaning set forth in the preamble.
           ------

          "Shelf Registration" shall have the meaning set forth in Section 4.
           ------------------

                                       3
<PAGE>

          "Shelf Request" shall have the meaning set forth in Section 4.
           -------------



     2.   Lock-up Agreement.
          -----------------

               (a)  Holder agrees that it shall not transfer, offer, pledge,
sell, contract to sell, grant any options for the sale of or otherwise dispose
of, directly or indirectly, any securities of the Company which Holder receives
upon any conversion or redemption of the Shares or exercise of the Warrant, in
each case for a period expiring 90 days after the date on which any such Company
securities are issued to Holder upon any and each such conversion, redemption or
exercise.

               (b)  Notwithstanding anything in this Agreement to the contrary,
in connection with any Offering, the Holder agrees that, if requested by the
managing underwriter of the Offering, the Holder shall not, directly or
indirectly, sell, offer, contract to sell, grant any option to purchase,
transfer the economic risk of ownership in, make any short sale, pledge or
otherwise dispose of, any Shares or Registrable Securities, without the prior
written consent of the managing underwriters of the Offering for a period of
ninety (90) days from the effective date of the registration statement under the
Securities Act relating to such Offering. This restriction shall be binding upon
any transferee of the Shares or Registrable Securities and the certificates for
the Shares or Registrable Securities shall bear a legend to such effect. In
order to enforce the foregoing covenant, the Company may impose stop-transfer
instructions with respect to the Shares or Registrable Securities until the end
of such period.

     3.   Demand for Registration.
          -----------------------

          (a)  Demand Period.  Until the date that is the second anniversary of
               -------------
the date of this Agreement (the "Demand Period"), subject to the terms and
                                 -------------
conditions set forth herein, the Holder shall have two (2) opportunities, in
addition to other rights enumerated in this Agreement, to have a registration
effected under the Securities Act of all or part of its Registrable Securities
(a "Demand Registration").
    -------------------

          (b)  Demand Procedure.
               ----------------

               (i) Subject to paragraph (ii) below, during the Demand Period the
Holder may deliver to the Company a written request ("Demand Registration
Request") requesting that the Company register any or all of the Holder's
Registrable Securities; provided, however, that the Company shall not be
                        --------  -------
required to comply with any Demand Registration Request unless the Holder
requests the registration of Registrable Securities having an aggregate Fair
Market Value in excess of (1) $5,000,000, with respect to the initial Demand
Registration, or (2) $5,000,000, with respect to the second Demand Registration.

                                       4
<PAGE>

          (ii)  No Demand Registration Request may be made within six (6) months
after any other Demand Registration is declared effective.  The Company shall
only be required to file one Registration Statement (as distinguished from
supplements or pre-effective or post-effective amendments thereto) in response
to each Demand Registration Request.

          (iii) A Demand Registration Request shall (1) set forth the number
of Registrable Securities intended to be sold pursuant to the Demand
Registration Request, (2) disclose whether all or any portion of a distribution
pursuant to such registration will be sought by means of an underwriting, and
(3) identify any underwriter or underwriters proposed for the underwritten
portion, if any, of such registration.

          (iv)  If the Company receives a Demand Registration Request in
compliance with the terms of this Agreement, then the Company shall, subject to
the limitations in paragraphs (v) and (vi) of this section, (1) use its
reasonable best efforts to prepare and file as soon as practicable with the SEC
a Registration Statement under the Securities Act with respect to all the
Registrable Securities that the Holder requested to be registered in the Demand
Registration Request, (2) use its reasonable best efforts to cause such
Registration Statement to become effective, and (3) keep such Registration
Statement effective until the earlier of (x) such time as the Holder shall have
sold or otherwise disposed of all of their Registrable Securities included in
the registration, or (y) sixty (60) days following the effective date of such
Registration Statement.  A registration requested pursuant to this paragraph
(iv) shall not be deemed to have been effected (1) unless a Registration
Statement with respect thereto has become effective or (2) if after it has
become effective, such registration is interfered with by any stop order,
injunction or other order or requirement of the SEC or other governmental agency
or court for any reason, unless (a) such order, injunction or requirement is
implemented after the period specified in clause (3) of the immediately
preceding sentence or (b) such order, injunction or requirement is lifted or
stayed within thirty (30) days.

          (v)   It is anticipated that the registration contemplated under this
Section 3 will be accomplished by means of the filing of a Form S-1 or such
other appropriate registration form under the Securities Act (1) as shall be
selected by the Company and (2) as shall permit the disposition of the
Registrable Securities being registered in accordance with the intended method
or methods of disposition.  In the event that Form S-3, or its successor form
under the Securities Act is then available to the Company, the Company shall use
such form.  If the Holder desires to distribute all or part of the Registrable
Securities covered by its request by means of an underwriting, they shall so
advise the Company in writing in their initial Demand Registration Request as
described in paragraph (iii) of this Section.  A determination of whether all or
part of the distribution will be by means of an underwriting shall be made by
the Holder, subject to the reasonable approval by the Company's Board of
Directors.  If all or part of the distribution is to be by means of an
underwriting, all subsequent decisions concerning the underwriting which are to
be made by the Holder pursuant to the terms of this Agreement, which shall
include the selection of the underwriter or underwriters to be engaged and the
representative, if any, of the underwriters so engaged, shall be made by the
Holder, subject to the reasonable approval by the Company's Board of Directors.

                                       5
<PAGE>

          (vi) If the parties agree to distribute all or part of the Registrable
Securities through an underwriting, the Holder shall enter into an underwriting
agreement consistent with the provisions of this Agreement and otherwise in
customary form with the underwriter or underwriters selected for such
underwriting.

     (c)  Priority on Demand Registration.  If a Demand Registration is an
          --------------------------------
          underwritten Offering and the managing underwriters advise the Company
          in writing that in their opinion the number of Registrable Securities
          exceeds the number of securities that can be sold in an orderly manner
          in such Offering within a price range acceptable to the Holder, the
          Company will include in such registration the number of shares of
          Registrable Securities requested to be included which, in the opinion
          of such underwriters, can be sold in an orderly manner within such
          acceptable price range.

     4.   Shelf Registration.
          ------------------

          (a)  Shelf Request.  If at any time the Company shall receive from a
               -------------
Holder a written request (a "Shelf Request") that the Company register pursuant
                             -------------
to Rule 415 under the Securities Act (or any successor rule with similar effect)
a delayed offering of all (but not less than all) Registrable Securities, then
the Company shall, as promptly as practicable (but in no event more than thirty
(30) days after so required or requested pursuant to this Section 4) prepare and
file with the SEC, and thereafter shall use its reasonable best efforts to cause
to be declared effective, a Registration Statement on an appropriate form under
the Securities Act relating to the offer and sale of Registrable Securities by
the Holder thereof from time to time in accordance with the methods of
distribution set forth in the Registration Statement and Rule 415 under the
Securities Act (hereinafter, the "Shelf Registration"). No Shelf Request may be
                                  ------------------
made within six (6) months after a Demand Registration is declared effective.

          (b)  Effective Time.  If the Company receives a Shelf Request in
               --------------
compliance with the terms of this Agreement, then the Company shall use its
reasonable best efforts to keep the Registration Statement filed pursuant to
this Section 4 continuously effective in order to permit the Prospectus to be
lawfully delivered by the Holder, for a period of two (2) years following the
latest date Shares were converted into Registrable Securities or such shorter
period that will terminate when all the Registrable Securities covered by the
Registration Statement (i) have been sold pursuant thereto, or (ii) are no
longer restricted securities (as defined in Rule 144 under the Securities Act,
or any successor rule thereof). The Company shall be deemed not to have used its
reasonable best efforts to keep the Registration Statement filed hereunder
effective during the requisite period if it voluntarily takes any action that
would result in the Holder not being able to offer and sell such Registrable
Securities during that period, unless such action is required by applicable law.

                                       6
<PAGE>

     5.   Piggyback Registrations.
          -----------------------

          (a) Right to Piggyback.  If the Company proposes to file any
              ------------------
registration statement under the Securities Act for purposes of an offering of
securities of the Company (including, but not limited to, registration
statements relating to secondary offerings of securities of the Company, but
excluding (i) Registration Statements filed pursuant to Section 3 or Section 4
of this Agreement or (ii) Registration Statements on Form S-8 (or any successor
form thereto) or with respect to corporate reorganizations or other transactions
under Rule 145 of the Securities Act) (a "Piggyback Registration"), the Company
                                          ----------------------
will give prompt written notice to the Holder of its intention to effect such a
registration (a "Piggyback Notice') and, subject to the terms hereof, the
                 ----------------
Company will include in such registration all Registrable Securities with
respect to which the Company has received a written request for inclusion
therein within fifteen (15) days after the date of delivery of the Piggyback
Notice.  The Company shall use its reasonable best efforts to keep any such
Registration Statement effective for up to sixty (60) days.  If the Piggyback
Registration is an underwritten offering on behalf of the Company, then the
Company shall not be required to include any Registrable Securities in such
offering unless the Holder enters into a customary form of underwriting
agreement in form and substance reasonably satisfactory to the underwriters and
the Company.

          (b) Priority on Primary Registrations.  If a Piggyback Registration is
              ---------------------------------
an underwritten primary registration on behalf of the Company, and the managing
underwriters advise the Company in writing that in their opinion the number of
securities requested to be included in such registration exceeds the number that
can be sold in an orderly manner in such offering within a price range
acceptable to the Company, the Company will include in such registration, (i)
first, the securities the Company proposes to sell, and (ii) second, other
securities requested to be included in such registration, including the
Registrable Securities (subject to any other priority arrangements existing
under registration rights agreements to which the Company is a party as of the
date hereof).

          (c) Priority on Secondary Registration.  If a Piggyback Registration
              ----------------------------------
is an underwritten secondary registration on behalf of holders of the Company's
securities other than the Holder (the "Other Holder"), and the managing
                                       ------------
underwriters advise the Company in writing that in their opinion the number of
securities requested to be included in such registration exceeds the number that
can be sold in an orderly manner in such offering within a price range
acceptable to the Other Holder requesting such registration, the Company will
include in such registration (i) first, the securities requested to be included
therein by the Other Holder requesting such registration, (ii) second, the
securities the Company proposes to sell, and (iii) third, other securities
requested to be included in such registration, including the Registrable
Securities (subject to any other priority arrangements existing under
registration rights agreements to which the Company is a party as of the date
hereof).

          (d) Selection of Underwriters.  In the case of an underwritten
              -------------------------
Piggyback Registration, the Company shall have the right to select the
investment banker(s) and manager(s) to administer the Offering.

                                       7
<PAGE>

     6.   Registration Procedures.
          -----------------------

          In connection with the obligations of the Company with respect to the
Registration Statements pursuant to this Agreement, the Company shall:

          (a) prepare and file with the SEC, within the time periods set forth
herein, a Registration Statement, which Registration Statement (i) shall be
available for sale of the subject Registrable Securities in accordance with the
intended method or methods of distribution by the Holder, and (ii) shall comply
as to form in all material respects with the requirements of the applicable form
and include all financial statements required by the SEC to be filed therewith;

          (b) subject to the last three sentences of this Section 6(b) and
Section 6(i) hereof, (i) prepare and file with the SEC such amendments and post-
effective amendments to each such Registration Statement as may be necessary to
keep such Registration Statement effective for the applicable period; (ii) cause
each such Prospectus to be supplemented by any required prospectus supplement,
and as so supplemented, to be filed pursuant to Rule 424 or any similar rule
that may be adopted under the Securities Act; (iii) respond as promptly as
practicable to any comments received from the SEC with respect to the
Registration Statement, or any amendment, post-effective amendment or supplement
relating thereto; and (iv) comply with the provisions of the Securities Act with
respect to the disposition of all securities covered by each Registration
Statement during the applicable period in accordance with the intended method or
methods of distribution by the selling holders thereof.  Notwithstanding
anything to the contrary contained therein, the Company shall not be required to
take any of the actions described in subsections (i), (ii), or (iii) above with
respect to Registrable Securities under a Demand Registration, Shelf
Registration or a Piggyback Registration unless and until the Company has
received a Demand Registration Request, Shelf Request or a Piggyback Notice from
the Holder that the Holder intends to make offers or sales under the
Registration Statement as specified in any such request or notice; provided,
                                                                   --------
however, that the Company shall have ten (10) business days to prepare and file
-------
any such amendment or supplement after receipt of the Demand Registration
Request, Shelf Request or Piggyback Notice.  Once the Holder has delivered a
Demand Registration Request, Shelf Request or Piggyback Notice to the Company,
the Holder shall promptly provide to the Company such information as the Company
reasonably requests in order to describe the Holder and the method of
distribution in a post-effective amendment to the Registration Statement or a
supplement to the Prospectus.  The Holder also shall notify the Company in
writing upon completion of such offer or sale or at such time as the Holder no
longer intends to make offers or sales under the Registration Statement;

          (c) furnish to the Holder, without charge, as many copies of each
Prospectus, including each preliminary Prospectus, and any amendment or
supplement thereto and such other documents as the Holder may reasonably
request, in order to facilitate the public sale or other disposition of the
Registrable Securities; the Company consents to the use of the Prospectus,
including each preliminary Prospectus, by the Holder in connection with the
offering and sale of the Registrable Securities covered by the Prospectus or the
preliminary Prospectus;

                                       8
<PAGE>

          (d) use its reasonable best efforts to register or qualify the
Registration Statement by the time the applicable Registration Statement is
declared effective by the SEC under all applicable state securities or blue sky
laws of such jurisdictions as the Holder shall reasonably request in writing,
keep each such registration or qualification effective during the period such
Registration Statement is required to be kept effective as provided herein and
all other acts and things that may be reasonably necessary or advisable to
enable the Holder to consummate the disposition in each such jurisdiction of
such Registrable Securities owned by the Holder to the extent required
hereunder; provided, however, that the Company shall not be required to (i)
           --------  -------
qualify generally to do business in any jurisdiction or to register as a broker
or dealer in such jurisdiction where it would not otherwise be required to
qualify but for this Section 6(d), (ii) subject itself to taxation in any such
jurisdiction, or (iii) submit to the general service of process in any such
jurisdiction.

          (e) notify the Holder promptly and, if requested by the Holder,
confirm such advice in writing (i) when a Registration Statement has become
effective and when any post-effective amendments and supplements thereto become
effective, (ii) of the issuance by the SEC or any state securities authority of
any stop order suspending the effectiveness of a Registration Statement or the
initiation of any proceedings for that purpose, (iii) if the Company receives
any notification with respect to the suspension of the qualification of the
Registrable Securities for sale in any jurisdiction or the initiation of any
proceeding for such purpose, and (iv) of the happening of any event during the
period a Registration Statement is effective as a result of which such
Registration Statement or the related Prospectus contains any untrue statement
of a material fact or omits to state any material fact required to be stated
therein or necessary to make the statements therein, in light of the
circumstances under which they were made (in the case of the Prospectus), not
misleading;

          (f) make every reasonable effort to obtain the withdrawal of any order
suspending the effectiveness of a Registration Statement at the earliest
possible moment;

          (g) furnish to the Holder, without charge, at least one conformed copy
of each Registration Statement and any post-effective amendment thereto (without
documents incorporated therein by reference or exhibits thereto, unless
requested);

          (h) cooperate with the Holder to facilitate the timely preparation and
delivery of certificates representing Registrable Securities to be sold and not
bearing any Securities Act legend; and enable certificates for such Registrable
Securities to be issued for such numbers of shares and registered in such name
as the Holder may reasonably request at least two business days prior to any
sale of Registrable Securities;

          (i) subject to the last three sentences of Section 6(b) hereof, upon
the occurrence of any event contemplated by Section 6(e)(iv) hereof, use its
reasonable best efforts promptly to prepare and file a supplement or prepare,
file and obtain effectiveness of a post-effective amendment to a Registration
Statement or the related Prospectus or any document incorporated therein by
reference or file any other required document so that, as thereafter delivered
to the purchasers of the Registrable Securities, such

                                       9
<PAGE>

Prospectus will not contain any untrue statement of a material fact or omit to
state a material fact required to be stated therein or necessary to make the
statements therein, in the light of the circumstances under which they were
made, not misleading;

          (j) make available for inspection by representatives of the Holder and
any counsel or accountant retained by the Holder, all financial and other
records and pertinent corporate documents of the Company, and cause the
officers, directors and employees of the Company to supply all information
reasonably requested by any such representative, counsel or accountant in
connection with a Registration Statement; provided, however, that such records,
                                          --------  -------
documents or information which the Company determines, in good faith, to be
confidential and notifies such representatives, counsel or accountants in
writing that such records, documents or information are confidential shall not
be disclosed by the representatives, counsel or accountants unless (i) the
disclosure of such records, documents or information is necessary to avoid or
correct a material misstatement or omission in a Registration Statement; (ii)
the release of such records, documents or information is ordered pursuant to a
subpoena or order from a court of competent jurisdiction; or (iii) such records,
documents or information have been generally made available to the public;

          (k) a reasonable time prior to the filing of any Registration
Statement, any Prospectus, any amendment to a Registration Statement or
amendment or supplement to a Prospectus, provide copies of such document (not
including any documents incorporated by reference therein unless requested) to
the Holder;

          (l) use its reasonable best efforts to cause all Registrable
Securities to be listed on any securities exchange on which similar securities
issued by the Company are then listed;

          (m) provide a CUSIP number for all Registrable Securities, not later
than the effective date of a Registration Statement;

          (n) otherwise use its reasonable best efforts to comply with all
applicable rules and regulations of the SEC and make available to its security
holders, as soon as reasonably practicable, an earnings statement covering at
least twelve (12) months that shall satisfy the provisions of Section 11(a) of
the Securities Act and Rule 158 thereunder; and

          (o) use its reasonable best efforts to cause the Registrable
Securities covered by the Registration Statement to be registered with or
approved by such other governmental agencies or authorities as may be necessary
by virtue of the business and operations of the Company to enable the Holder to
consummate the disposition of its Registrable Securities.

          The Company may require the Holder to furnish to the Company in
writing such information regarding the proposed distribution by the Holder of
the Registrable Securities as the Company may from time to time reasonably
request in writing.

                                       10
<PAGE>

          In connection with and as a condition to the Company's obligations
with respect to the Registration Statement, the Holder agrees that:  (i) it will
not offer or sell its Registrable Securities under the Registration Statement
until it has provided a Demand Registration Request, Shelf Request or a
Piggyback Notice, if and to the extent applicable, and has received copies of
the supplemental or amended Prospectus contemplated by Section 6(b) hereof and
receives notice that any post-effective amendment has become effective; (ii)
upon receipt of any notice from the Company of the happening of any event of the
kind described in Section 6(e)(iv) hereof, the Holder will forthwith discontinue
disposition of Registrable Securities pursuant to a Registration Statement until
the Holder receives copies of the supplemental or amended Prospectus
contemplated by Section 6(i) hereof and receives notice that any post-effective
amendment has become effective, and, if so directed by the Company, the Holder
will deliver to the Company (at the expense of the Company) all copies in its
possession, other than permanent file copies then in the Holder's possession, of
the Prospectus covering such Registrable Securities current at the time of
receipt of such notice; and (iii) all offers and sales under the Registration
Statement shall be completed within sixty (60) days after the first date on
which offers or sales can be made pursuant to clause (i) above, and upon
expiration of such sixty (60) day period the Holder will not offer or sell its
Registrable Securities under the Registration Statement until it has again
complied with the provisions of clause (i) of this paragraph.

     Notwithstanding anything to the contrary contained herein, the Company
shall have the right to postpone the filing of any Registration Statement
hereunder for a reasonable period of time (not exceeding sixty (60) days) if the
Company furnishes the Holder a certificate signed by the Chairman of the Board
of Directors or the President of the Company stating that in its good faith
judgment, the Company's Board of Directors (or the executive committee thereof)
has determined that effecting the registration at such time would adversely
affect a material financing, acquisition or disposition of assets or securities,
merger or other comparable transaction, or would require the Company to make
public disclosure of information the public disclosure of which would have a
material adverse effect upon the Company.

     Notwithstanding anything to the contrary contained herein, the Company
shall cause each Registration Statement and the related Prospectus and any
amendment or supplement thereto, as of the effective date of the Registration
Statement, amendment or supplement, (i) to comply in all material respects with
the applicable requirements of the Securities Act and the rules and regulations
of the SEC, and (ii) not to contain any untrue statement of a material fact or
omit to state a material fact required to be stated therein or necessary in
order to make the statements therein, in light of the circumstances under which
they were made,  not misleading.

     7.   Investment Representations.  With respect to the Shares and the
          --------------------------
Registrable Securities, the Holder represents and warrants as follows:

          (a) The Holder, by reason of its business and financial experience,
has such knowledge, sophistication and experience in financial and business
matters and in making investment decisions of this type that it is capable of
(i) evaluating the merits and

                                       11
<PAGE>

risks of an investment in the Shares and making an informed investment decision,
(ii) protecting its own interest and (iii) bearing the economic risk of such
investment.

          (b) The Holder is acquiring the Shares for investment for the Holder's
own account, not as a nominee or agent and not with the view to, or any
intention of, a resale or distribution thereof, in whole or in part, or the
grant of any participation therein.  The Holder understands that, except as
expressly provided herein, the Shares have not been registered under the
Securities Act or state securities laws by reason of a specific exemption from
the registration provisions of the Securities Act and applicable state
securities laws that depends upon, among other things, the bona fide nature of
the investment intent and the accuracy of the Holder's representations as
expressed in this Agreement.  The Holder further understands that except as
expressly provided herein the Company shall have no obligation to register the
Shares or the Registrable Securities under the Securities Act or any state
securities laws or to take any action that would make available any exemption
from the registration requirements of such laws.  The Holder hereby acknowledges
that because of the restrictions on transfer or assignment of the Shares to be
issued in connection with the Purchase, the Holder may have to bear the economic
risk of the investment commitment in the Shares for an indefinite period of
time.

          (c) The Holder will observe and comply with the Securities Act and all
applicable state securities and blue sky laws and the rules and regulations
promulgated thereunder, as now in effect and as from time to time amended, in
connection with any offer, sale, pledge, transfer or other disposition of the
Shares or the Registrable Securities.  In furtherance of the foregoing, and in
addition to any restrictions contained in this Agreement, the Holder will not
offer to sell, exchange, transfer, pledge, or otherwise dispose of any of the
Shares or the Registrable Securities unless at such time at least one of the
following is satisfied:

              (i)   a Registration Statement under the Securities Act covering
the Shares or the Registrable Securities proposed to be sold, transferred or
otherwise disposed of, describing the manner and terms of the proposed sale,
transfer or other disposition, and containing a current Prospectus, shall have
been filed with the SEC and made effective under the Securities Act;

              (ii)  such transaction shall be permitted pursuant to the
provisions of Rule 144;

              (iii) counsel representing the Holder, satisfactory to the
Company, shall have advised the Company in a written opinion letter reasonably
satisfactory to the Company and its counsel, and upon which the Company and its
counsel may rely, that no registration under the Securities Act or any
applicable state securities law would be required in connection with the
proposed sale, transfer or other disposition; or

              (iv)  an authorized representative of the SEC shall have rendered
written advice to the Holder (sought by the Holder or counsel to the Holder,
with a copy

                                       12
<PAGE>

thereof and of all other related communications delivered to the Company) to the
effect that the SEC would take no action, or that the staff of the SEC would not
recommend that the SEC take action, with respect to the proposed sale, transfer
or other disposition if consummated.

          (d) The Holder understands that an investment in the Shares involves
substantial risks.  Holder has been given the opportunity to make a thorough
investigation of the proposed activities of the Company and, upon request to the
Company, has been furnished with materials relating to the Company and its
proposed activities, including, without limitation, a copy of the Prospectus
dated May 20, 1999 (the "CAIS Prospectus") and all reports filed by the Company
with the SEC since May 20, 1999 (the "CAIS SEC Reports").  The Holder has been
afforded the opportunity to obtain any additional information deemed necessary
by the Holder to verify the accuracy of any representations made or information
conveyed to the Holder.  The Holder confirms that all documents, records and
books pertaining to its investment in the Shares and requested by the Holder
have been made available or delivered to the Holder.  The Holder has had an
opportunity to ask questions of and receive answers from the Company, or from a
person or persons acting on the Company's behalf, concerning the terms and
conditions of this investment.  The Holder has relied upon, and is making its
investment decision upon, the CAIS Prospectus, the CAIS SEC Reports, the
representations and warranties of the Company set forth in the Purchase
Agreement and other information publicly available about the Company.

          (e) The Holder has no knowledge of any causes of action or other
claims that could have been or in the future might be asserted by the Holder
against the Company or any of its predecessors, successors, assigns, directors,
employees, agents or representatives arising out of facts or circumstances
occurring at any time on or prior to the date hereof and in any way relating to
any duty or obligation of the Holder.

     8.   Restrictive Legend.  All certificates representing the Shares
          ------------------
deliverable to the Holder pursuant to the Purchase Agreement and any
certificates subsequently issued with respect thereto or in substitution
therefor, unless a sale, transfer or other disposition is executed pursuant to
one or more of the alternative conditions set forth in Section 6(c) shall have
occurred, or unless the conditions of paragraph (k) of Rule 144 promulgated
under the Securities Act shall have been satisfied, shall bear a legend
substantially as follows, in addition to any legend the Company determines is
required pursuant to any applicable legal requirement:

     "The shares represented by this certificate may not be offered,
     sold, pledged, transferred or otherwise disposed of except in
     accordance with the requirements of the Securities Act of 1933,
     as amended, and the other conditions specified in that certain
     Series F Convertible Participating Preferred Stock Purchase
     Agreement dated as of April 28, 2000 and that certain
     Registration Rights Agreement dated as of April 28, 2000, copies
     of which agreements CAIS Internet, Inc. will furnish, without
     charge, to the holder of this certificate upon written request
     therefor."

                                       13
<PAGE>

The Company, at its discretion, may cause a stop transfer order to be placed
with its transfer agent with respect to the certificates for the Shares but not
as to the certificates for any part of the Shares as to which said legend is no
longer appropriate when one or more of the alternatives set forth in Section
7(c) shall have been satisfied or the conditions of paragraph (k) of Rule 144
promulgated under the Securities Act shall have been satisfied.

     9.   Indemnification; Contribution.
          -----------------------------

          (a) Indemnification by the Company.  The Company agrees to indemnify
              ------------------------------
and hold harmless the Holder and its officers and directors and each Person, if
any, who controls the Holder within the meaning of Section 15 of the Securities
Act as follows:

              (i)   against any and all loss, liability, claim, damage and
expense whatsoever, as incurred, arising out of any untrue statement or alleged
untrue statement of a material fact contained in any Registration Statement (or
any amendment thereto) pursuant to which the Holder's Registrable Securities
were registered under the Securities Act, including all documents incorporated
therein by reference, or the omission or alleged omission therefrom of a
material fact required to be stated therein or necessary to make the statements
therein not misleading or arising out of any untrue statement or alleged untrue
statement of a material fact contained in any Prospectus (or any amendment or
supplement thereto), including all documents incorporated therein by reference,
or the omission or alleged omission therefrom of a material fact necessary in
order to make the statements therein, in the light of the circumstances under
which they were made, not misleading;

              (ii)  against any and all loss, liability, claim, damage and
expense whatsoever, as incurred, to the extent of the aggregate amount paid in
settlement of any litigation, or investigation or proceeding by any governmental
agency or body, commenced or threatened, or of any claim whatsoever based upon
any such untrue statement or omission, if such settlement is effected with the
written consent of the Company; and

              (iii) against any and all expense (including reasonable fees and
disbursements of counsel), as reasonably incurred in investigating, preparing or
defending against any litigation, or investigation or proceeding by any
governmental agency or body, commenced or threatened, in each case whether or
not a party, or any claim whatsoever based upon any such untrue statement or
omission, or any such alleged untrue statement or omission, to the extent that
any such expense is not paid under subparagraph (i) or (ii) above, provided,
                                                                   --------
however, that the indemnity provided pursuant to this Section 9(a) does not
-------
apply to the Holder with respect to any loss, liability, claim, damage or
expense to the extent arising out of any untrue statement or omission or alleged
untrue statement or omission made in reliance upon and in conformity with
written information furnished to the Company by the Holder expressly for use in
a Registration Statement (or any amendment thereto) or any Prospectus (or any
amendment or supplement thereto).

                                       14
<PAGE>

          (b) Indemnification by Holder.  The Holder agrees to indemnify and
              -------------------------
hold harmless the Company and its directors and officers (including each
director and officer of the Company who signed the Registration Statement), and
each Person, if any, who controls the Company within the meaning of Section 15
of the Securities Act, to the same extent as the indemnity contained in Section
9(a) hereof (except that any settlement described in Section 9(a)(ii) shall be
effected with the written consent of the Holder), but only insofar as such loss,
liability, claim, damage or expense arises out of or is based upon any untrue
statement or omission, or alleged untrue statement or omission, made in a
Registration Statement (or any amendment or supplement thereto) in reliance upon
and in conformity with written information furnished to the Company by the
Holder expressly for use in such Registration Statement (or amendment thereto)
or such Prospectus (or any amendment or supplement thereto).  In no event shall
the liability of the Holder under this Section 9(b) be greater in amount than
the dollar amount of the proceeds received by the Holder upon the sale of the
Registrable Securities giving rise to such indemnification obligation.

          (c) Conduct of Indemnification Proceedings.  Each indemnified party
              --------------------------------------
shall give reasonably prompt notice to the indemnifying party of any action or
proceeding commenced against it in respect of which indemnity may be sought
hereunder, but failure to so notify the indemnifying party (i) shall not relieve
it from any liability that it may have under the indemnity agreement provided in
Section 9(a) or (b) above, unless and to the extent it did not otherwise learn
of such action and the lack of notice by the indemnified party results in the
forfeiture by the indemnifying party of substantial rights and defenses and (ii)
shall not relieve, in any event, the indemnifying party from any obligations to
the indemnified party other than the indemnification obligation provided under
Section 9(a) or (b) above.  If the indemnifying party so elects within a
reasonable time after receipt of such notice, the indemnifying party may assume
the defense of such action or proceeding at the indemnifying party's own expense
with counsel chosen by the indemnifying party and approved by the indemnified
party defendant in such action or proceeding, which approval shall not be
unreasonably withheld; provided, however, that, if the indemnified party
                       --------  -------
reasonably determines that a conflict of interest exists where it is advisable
for such indemnified party to be represented by separate counsel or that, upon
advice of counsel, there may be legal defenses available to it that are
different from or in addition to those available to the indemnifying party, then
the indemnifying party shall not be entitled to assume such defense and the
indemnified party shall be entitled to one separate counsel at the indemnifying
party's expense.  If the indemnifying party is not entitled to assume the
defense of such action or proceeding as a result of the proviso to the preceding
sentence, the indemnifying party's counsel shall be entitled to conduct the
indemnifying party's defense and counsel for the indemnified party shall be
entitled to conduct the defense of the indemnified party, it being understood
that both such counsel will cooperate with each other to conduct the defense of
such action or proceeding as efficiently as possible.  In such event, however,
no indemnifying party will be liable for any settlement effected without the
written consent of the indemnifying party.  If the indemnifying party is
entitled to assume, and assumes, the defense of such action or proceeding in
accordance with this paragraph, the indemnifying party shall not be liable for
the fees and expenses of counsel for the indemnified party incurred thereafter
in connection with such action or proceeding.

                                       15
<PAGE>

          (d) Contribution.  In order to provide for just and equitable
              ------------
contribution in circumstances in which the indemnity agreement provided for in
this Section 8 is held to be unenforceable for any reason even though it is
applicable in accordance with its terms, the Company and the Holder shall
contribute to the aggregate losses, liabilities, claims, damages and expenses of
the nature contemplated by this indemnity agreement incurred by the Company and
the Holder, in such proportion as is appropriate to reflect the relative fault
of and benefits to the Company on the one hand and the Holder on the other, in
connection with the statements or omissions that resulted in such losses,
claims, damages, liabilities or expenses, as well as any other relative
equitable considerations.  The relative benefits to the indemnifying party and
indemnified party shall be determined by reference to, among other things, the
total proceeds received by the indemnified party and the indemnifying party in
connection with the Offering to which such losses, claims, damages, liabilities
or expenses relate.  The relative fault of the indemnifying party and the
indemnified party shall be determined by reference to, among other things,
whether the action in question, including any untrue or alleged untrue statement
of a material fact or omission or alleged omission to state a material fact, has
been made by, or relates to information supplied by, the indemnifying party or
the indemnified party, and the parties' relative intent, knowledge, access to
information and opportunity to correct or prevent such action.

          The parties hereto agree that it would not be just or equitable if
contribution pursuant to this Section 9(d) were determined by pro rata
allocation or by any other method of allocation that does not take account of
the equitable considerations referred to in the immediately preceding paragraph.
Notwithstanding the provisions of this Section 9(d), the Holder shall not be
required to contribute any amount in excess of the amount by which the total
price at which the Registrable Securities were offered to the public exceeds the
amount of any damages that the Holder has otherwise been required to pay by
reason of such untrue statement or omission.

          Notwithstanding the foregoing, no Person guilty of fraudulent
misrepresentation (within the meaning of Section 11(f) of the Securities Act)
shall be entitled to contribution from any Person who was not guilty of such
fraudulent misrepresentation.  For purposes of this Section 9(d), each Person,
if any, who controls a holder within the meaning of Section 5 of the Securities
Act and directors and officers of a holder shall have the same rights to
contribution as such holder, and each director of the Company, each officer of
the Company who signed the Registration Statement and each Person, if any, who
controls the Company within the meaning of Section 15 of the Securities Act
shall have the same rights to contribution as the Company.

     10.  Rule 144 Sales.
          --------------

          (a) The Company covenants that it will file the reports required to be
filed by the Company under the Securities Act and the Securities Exchange Act,
as amended, so as to enable the Holder to sell the Registrable Securities
pursuant to Rule 144 under the Securities Act, to the extent such securities are
otherwise transferable.

                                       16
<PAGE>

          (b) In connection with any sale, transfer or other disposition by the
Holder of any Registrable Securities pursuant to Rule 144 under the Securities
Act, the Company shall cooperate with the Holder to facilitate the timely
preparation and delivery of certificates representing Registrable Securities to
be sold and not bearing any Securities Act legend, and enable certificates to be
for such number of shares and registered as the Holder may reasonably request at
least two business days prior to any sale of Registrable Securities.

     11.  Miscellaneous.
          -------------

          (a) Amendments and Waivers.  The provisions of this Agreement,
              ----------------------
including the provisions of this sentence, may not be amended, modified or
supplemented, and waivers or consents to departures from the provisions hereof
may not be given, without the written consent of the Company and the Holder.
Notice of any amendment, modification or supplement to this Agreement adopted in
accordance with this Section 10(a) shall be provided by the Company to the
Holder at least ten (10) days prior to the effective date of such amendment,
modification or supplement.

          (b) Notices.  All notices and other communications provided for or
              -------
permitted hereunder shall be made in writing by hand-delivery, registered first-
class mail, telex, telecopier, or any courier guaranteeing overnight delivery,
(i) if to the Holder, at the most current address given by the Holder to the
Company by means of a notice given in accordance with the provisions of this
Section 11(b), or (ii) if to the Company, at 1255 22/nd/ Street, N.W.,
Washington, D.C.  20037, Attention:  Chief Executive Officer.

          All such notices and communications shall be deemed to have been duly
given:  at the time delivered by hand, if personally delivered; five business
days after being deposited in the mail, postage prepaid, if mailed; when
answered back, if telexed; when receipt is acknowledged, if telecopied; or at
the time delivered if delivered by an air courier guaranteeing overnight
delivery.

          (c) Successors and Assigns.  This Agreement shall inure to the benefit
              ----------------------
of and be binding upon the successors and permitted assigns as permitted
hereunder of each of the parties and, except as provided in Section 9 hereof, no
other Person shall acquire or have any right under or by virtue of this
Agreement.  No purchaser of the Shares from the Holder shall be deemed a
successor or assign by reason of such purchase.  The benefits and obligations of
the Holder under this Agreement may be assigned only by a written instrument
signed by the Holder and such assignee.  If any successor or such an assignee of
the Holder shall acquire Registrable Securities, whether by operation of law or
otherwise, such Registrable Securities shall be held subject to all of the terms
of this Agreement.

          (d) Counterparts.  This Agreement may be executed in any number of
              ------------
counterparts and by the parties hereto in separate counterparts, each of which
when so executed shall be deemed to be an original and all of which taken
together shall constitute one and the same agreement.

                                       17
<PAGE>

          (e) Headings.  The headings in this Agreement are for convenience of
              --------
reference only and shall not limit or otherwise affect the meaning hereof.

          (f) GOVERNING LAW.  THIS AGREEMENT SHALL BE GOVERNED BY AND CONSTRUED
              -------------
IN ACCORDANCE WITH THE LAWS OF THE STATE OF DELAWARE WITHOUT GIVING EFFECT TO
THE CONFLICTS OF LAW PROVISIONS THEREOF.

          (g) Specific Performance.  The parties hereto acknowledge that there
              --------------------
would be no adequate remedy at law if either party fails to perform any of its
obligations hereunder, and accordingly agree that each party, in addition to any
other remedy to which it may be entitled at law or in equity, shall be entitled
to compel specific performance of the obligations of the other party under this
Agreement in accordance with the terms and conditions of this Agreement in any
court of the United States or any State thereof having jurisdiction.

          (h) Entire Agreement.  This Agreement is intended by the parties as a
              ----------------
final expression of their agreement and intended to be a complete and exclusive
statement of the agreement and understanding of the parties hereto in respect of
the subject matter contained herein.  This Agreement supersedes all prior
agreements and understandings between the parties with respect to such subject
matter.

          (i) Additional Actions and Documents.  The parties hereto shall take
              --------------------------------
or cause to be taken such further actions, shall execute, deliver and file, or
cause to be executed, delivered or filed, such further documents and
instruments, and shall obtain such consents as may be necessary or as the other
party may reasonably request, without the payment of further consideration, in
order fully to effectuate the purposes, terms and conditions of this Agreement.


                   [Signatures appear on the following page]

                                       18
<PAGE>

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

                         CAIS INTERNET, INC.

                         By:   /s/ Gary H. Rabin
                               ________________________
                         Name: Gary H. Rabin
                               ________________________
                         Its:  Executive Vice President
                               ________________________

                         MICROSOFT CORPORATION

                         By:   /s/ John G. Connors
                               ________________________
                         Name: John G. Conners
                               ________________________
                         Its:  Chief Financial Officer
                               ________________________


                         Address:

                         MicroSoft Corporation
                         One MicroSoft Way
                         Redmond, Washington  98052

                                       19