<PAGE>
 
                                                                   Exhibit 10.16


                                  [IMSS LOGO]

                    Information Management System Services

                                     a division of R.J. Reynolds Tobacco Company








--------------------------------------------------------------------------------

                                                              Services Agreement

--------------------------------------------------------------------------------
<PAGE>
 

                                                         IMSS Services Agreement
--------------------------------------------------------------------------------


<TABLE>
<CAPTION>
Table of Contents

<S>                                                                         <C>
TERM........................................................................   1

ARTICLE I. AGREEMENT........................................................   1
1.1  Services...............................................................   1

ARTICLE 2. DEFINITIONS......................................................   1

ARTICLE 3. SERVICES AND EQUIPMENT TO BE PROVIDED BY IMSS....................   2
3.1  Services...............................................................   2
3.2  Equipment..............................................................   4

ARTICLE 4. SOFTWARE AND RELATED PROPRIETARY RIGHTS..........................   4
4.1  IMSS Software..........................................................   4
4.2  Customized Software....................................................   4
4.3  Customer Software......................................................   5

ARTICLE 5. CUSTOMER'S OBLIGATIONS...........................................   5
5.1  Customer's Obligations.................................................   5

ARTICLE 6. CUSTOMER PROTECTION..............................................   6
6.1  Customer Data..........................................................   6
6.2  Safeguarding Customer Data.............................................   6
6.3  Confidentiality........................................................   6
6.4  Exclusivity of IMSS' Services..........................................   6

ARTICLE 7. PAYMENTS TO IMSS.................................................   7
7.1  Monthly Charges........................................................   7
7.2  Special Services Charges...............................................   7
7.3  Reruns.................................................................   7
7.4  Time and Manner of Payment.............................................   7
7.5  Taxes, Travel and Living Expenses......................................   7

ARTICLE 8. WARRANTY AND MAINTENANCE.........................................   8

ARTICLE 9. PERFORMANCE REVIEW AND TERMINATION...............................   8
9.1  Performance Review.....................................................   8
9.2  Transition.............................................................   8
9.3  Termination for Cause..................................................   9
9.4  Termination for Nonpayment.............................................   9
9.5  Rights Upon Termination................................................   9

ARTICLE 10. REMEDIES........................................................  10
10.1 Measure of Damages.....................................................  10

ARTICLE 11. INDEMNITIES.....................................................  10
11.1 Indemnity by Customer..................................................  10
11.2 Indemnity by IMSS......................................................  10
11.3 Mutual Indemnity.......................................................  11

ARTICLE 12. MISCELLANEOUS...................................................  11
12.1 Binding Nature and Assignment..........................................  11
12.2 Notices................................................................  11
12.3 Relationship of Parties................................................  11
12.4 Force Majeure..........................................................  12
12.5 Attorney's Fees........................................................  12
12.6 Media Releases.........................................................  12
12.7 Entire Agreement.......................................................  12
</TABLE>

Page i
<PAGE>
 
                                                         IMSS Services Agreement
--------------------------------------------------------------------------------





                               Service Agreement

This Agreement made effective as of the 1st day of June, 1997, (hereinafter 
referred to as the "Effective Date"), by and between INFORMATION MANAGEMENT 
SYSTEM SERVICES, a division of R.J. Reynolds Tobacco Company, a corporation 
organized and existing under the laws of the State of New Jersey, and having a 
principal place of business at 401 North Main Street, Winston-Salem, NC 27102 
(hereinafter referred to as "IMSS"), and BLUE RHINO CORPORATION, a corporation 
organized and existing under the laws of the State of Delaware, and having its 
principal place of business at 104 Cambridge Plaza Drive, Winston-Salem, NC 
27104 (hereinafter referred to as "Customer").


Term

This Agreement shall begin on the effective date set forth above and shall end 
on the 31st day of May 2000. This Agreement shall automatically renew itself on 
each anniversary of the effective date unless either party terminates it. Either
party may terminate this Agreement for any reason but such termination shall be 
effective only if the terminating party gives written notice of its intent to 
terminate at least ninety (90) days prior to the date of such termination and 
the date of termination is an anniversary of the effective date, if date of 
termination is other than an anniversary date the terminating party gives 
written notice of its intent to terminate at least one hundred and eighty (180) 
days prior to the date of such termination. There can be no termination before 
the last to expire of any Equipment Schedule or third party Software license 
entered into pursuant to this Agreement unless the parties expressly agree to 
the contrary and Customer agrees to bear any early termination fee associated 
with any Equipment Schedule or third party Software license in effect pursuant 
to this Agreement.


Article 1. Agreement

1.1 Services

During the term of this Agreement, IMSS shall supply to Customer and Customer 
shall purchase from IMSS those electronic data processing ("DP") and 
telecommunications services and products described in Article 3 of this 
Agreement (collectively, the "Services") and certain other services as are 
described elsewhere in this Agreement.


Article 2. Definitions

     2.1  "Account Manager" shall mean the IMSS employee designated by IMSS to 
serve as Customer's primary point of contact for all matters pertaining to this 
Agreement. 

     2.2  "Application Specifications" shall mean the functional, performance 
and operational characteristics of Software, described in a document such as a 
functional specifications document or a detailed design document. 

Page 1 of 12                                               
<PAGE>
 
                                                         IMSS Services Agreement
--------------------------------------------------------------------------------

     2.3   "Application" shall mean a computer system used to accomplish
business objectives, such as general ledger.

     2.4   "Customer Software" shall mean computer systems or programs that are
owned by the Customer or a third party and due to such ownership would require a
license or consent for use for others. Such Software will be listed on a
schedule to this Agreement.

     2.5   "Customized Software" shall mean any Software created by IMSS for the
exclusive use of Customer and does not utilize modified or otherwise any
component, concept or process owned by or the property of IMSS.

     2.6   "Equipment" shall mean that computer hardware and other equipment
provided to Customer from IMSS as listed in a schedule to this Agreement.

     2.7   "IMSS Data Center" shall mean any location under the control of IMSS
where IMSS performs Services for Customer.

     2.8   "IMSS Software" shall mean Software owned by IMSS that is modified by
IMSS for use by or for Customer and is licensed to Customer.

     2.9   "Maintenance" shall mean any correction or modification of existing
Software to correct bugs or errors which does not materially improve or add
functionality or a feature to the Software.

     2.10  "Modifications" shall mean any improvements, modifications, or other
changes in the Software which change the basic program function or feature of
the Software originally provided to the Customer. Customer shall obtain such
changes at IMSS' Special Services Charges set forth in section 7.2 below for
installing such changes.

     2.11  "Monthly Charges" shall mean the fixed monthly charges specified in a
schedule to this Agreement to be paid to IMSS by Customer for Services within
the baseline level of Services.

     2.12  "Required Consent" shall mean the authorization from third parties
for IMSS to use applicable Equipment and Software belonging to such third
parties for the rendition of Services to Customer.

     2.13  "Returns" shall mean the processing of data more than once or after
the original process has occurred.

     2.14  "Software" shall mean computer programs, the tangible media on which
they are recorded, and their supporting documentation, including input and
output screen formats and program listings.

     2.15  "Special Services" shall mean any services requested by Customer
outside the scope of Services covered by the Monthly Charges or one-time
Charges.


Article 3.  Services and Equipment to be Provided by IMSS

3.1  Services

     During the term of this Agreement, IMSS shall provide Services to Customer,
each defined in written Schedules to this Agreement, which Schedules may be
revised from time to time by mutual consent of the parties, examples of such
Schedules are as follows:

     a.  IMSS shall, at Customer's request, provide consultation and perform
Application Software design and development activities. IMSS and Customer will
jointly develop Application Specifications for the projects


Page 2 of 12    

<PAGE>
 

                                                         IMSS Services Agreement
--------------------------------------------------------------------------------


identified on a schedule to this Agreement. Any Application Software development
project must be authorized in advance pursuant to procedure described in Section
3.1.m of this Agreement.

     b. Install each IMSS or third party Software listed on a schedule to this
Agreement and operate that Software for Customer after its implementation,
accepting input and delivering output at the IMSS Data Center.

     c. Provide Maintenance (after warranty expiration) on the Software
developed by IMSS for Customer at Customer's option.

     d. Make Modifications (other than Maintenance) or perform development or
conversions of Customer Software, third party Software (when allowed by the
third party license) or IMSS' Software when Customer authorizes them in writing.

     e. Prepare Software functional requirements, supporting specifications and
acceptance criteria.

     f. Perform Reruns as required by program errors resulting from the fault of
IMSS, without additional charge to Customer, if brought to the attention of IMSS
within the times set forth in Section 5.1.b. IMSS' sole liability for such
errors shall be to rerun the application and supply the correct output.

     g. Operate, manage and maintain the Customer Telecommunications Network
designed and implemented by IMSS, as outlined in a schedule to this Agreement.
The "Customer Telecommunications Network" shall mean and consist of all
Equipment (including multiplexors, modems and digital service units), software,
circuits to locations of the Customer which are used to connect and transmit
data between the IMSS Data Center and any remote end-user locations.

     h. Store and safeguard storage media containing the Customer's data when in
the custody of IMSS in accordance with the safeguards specified in Section 6.2
of this Agreement.

     i. Maintain and update as agreed upon by both parties, user documentation
for all Software (and Modifications to it) used to perform Services, for as long
as IMSS operates such Software for Customer under this Agreement.

     j. Conduct training for Customer's employees in the use of any Software
developed and implemented by IMSS during the term of this Agreement so that such
employees may train other Customer's employees. Any training requested or
required by Customer beyond the levels specified in the preceding sentence, or
not covered by the Monthly Charges or one-time charges will be provided by IMSS
as a Special Services Charge.

     k. Provide HELP Desk support to Customer.

     l. Provide Personal Computer Depot Maintenance and Installation to remote
locations.

     m. At Customer's request, IMSS may perform Special Services. Upon receiving
a request for additional work, IMSS will advise Customer in writing in five
business days that the additional work is a Special Service and IMSS' intent to
perform or not perform such work. If IMSS elects to perform the Special Service,
it shall provide to Customer in a reasonable period of time a description of the
work to be performed, a timetable (which will be based on the complexity of the
request) for its performance, and the reasonable charges for the Special
Services. Upon receiving (I) Customer's written authorization to proceed and
agreement to pay IMSS' charges,



Page 3 of 12                                                      
<PAGE>
 
and (ii) Application Specifications, where appropriate, the parties shall 
execute a Schedule to this Agreement setting forth the terms and conditions 
applicable to such Services, and IMSS will perform the Services.

3.2 Equipment
IMSS may furnish to Customer the personal computers and other Equipment 
necessary for, and associated with, the furnishing of the Services. Such 
equipment and the costs and charges to be paid by Customer are set forth on a 
schedule to this Agreement.

Article 4. Software and Related Property Rights

4.1  IMSS Software
     a. IMSS Software is and shall remain IMSS' property. For a reasonable 
license fee, IMSS shall grant to Customer a perpetual, non-transferable, 
nonexclusive license to use the IMSS Software (including all related 
documentation) used by IMSS in providing Services to the Customer. This license 
grant is contingent upon Customer and IMSS entering into a license agreement, in
form and substance reasonably satisfactory to IMSS and Customer. If appropriate,
IMSS and Customer will pursue approaches to provide a copy of the source code to
Customer.

     b. Customer shall keep the IMSS Software confidential and shall not at any 
time allow the IMSS Software, any of its components or any modifications to it, 
to be disclosed to third parties, sold, assigned, leased or commercially 
exploited or marketed in any way, with or without charge, by Customer or its 
employees or agents. Except to the extent required for normal operation of IMSS 
Software, Customer shall not permit the IMSS Software to be copied or 
reproduced, in whole or in part, by any person or entity at any time.

     c. Customer agrees that the IMSS Software is the valuable property of IMSS,
that any unauthorized disclosure of the IMSS Software would cause IMSS 
irreparable injury for which IMSS would have no adequate remedy at law, and 
that IMSS shall be entitled to preliminary and other injunctive relief against 
any such disclosure. Such injunctive relief shall be in addition to, and in no 
way in limitation of, any other remedies or rights which IMSS may have at law,
in equity or otherwise.

4.2 Customized Software
Upon payment by Customer of all fees associated with the development of  
Customized Software, IMSS shall provide to Customer all Software, documentation 
and such related items including a copy of the source code created by IMSS. Such
Customized Software is considered the sole property of the Customer and its 
further disposition is deemed to be at Customer's discretion. Should Customer 
terminate this Agreement before its expiration, Customer may take possession of,
and title to, all Customized Software for which Customer has paid IMSS in 
whatever state of development it may be at the time of Customer's termination. 
Provided, however,





Page 4 of 12  











<PAGE>
 
                                                        IMSS Services Agreement 


Customer hereby grants to IMSS a perpetual, non-transferable, non-exclusive 
license to use the Customized Software (including all related documentation) 
subject to the provisions of Section 6.4 below.

4.3 Customer Software
Customer grants to IMSS at no charge to IMSS, the unrestricted, exclusive right 
to use the Customer Software necessary for IMSS to provide services as 
contemplated by this Agreement. If Customer does not have the authority to grant
access and use to any of the Customer Software, Customer, at its sole cost and 
expense, shall use its best efforts to obtain Required Consents for such access 
and use. In the event that any Required Consent is not obtained, the parties 
shall cooperate with each other in achieving a reasonable alternative 
arrangement. If such Required Consent is not attainable and no alternative 
arrangement is achieved, IMSS shall be excused from performing any Services 
required by this Agreement if the performance of such Services is dependent upon
obtaining Required Consent(s) and IMSS' nonperformance will not be deemed to be 
a breach of this Agreement or grounds for termination of this Agreement by 
Customer.

Article 5. Customer's Obligations

5.1 Customer's Obligations
Customer will, on a timely basis:
     a. Supply to IMSS for processing, as required by IMSS, complete and 
accurate source data and machine-readable data with applicable control totals 
for Customer Software, and in the form reasonably required by IMSS for other 
Software.

     b. Review all production output prepared by IMSS and identify all incorrect
or incomplete production output within five (5) business days after receipt for 
daily and weekly output, with ten (10) business days after receipt for monthly 
output and within fifteen (15) business days for quarterly, annual or other 
output. Failure to identify any incorrect or incomplete production output within
the specified time shall constitute acceptance of such production output.

     c. Maintain procedures manuals provided to Customer by IMSS by
 distributing updates provided by IMSS.

     d. Approve all Application Specifications for Software and Special 
Services. Except for specifications pertaining to Customer's operating 
telecommunication network and hardware configuration, Customer shall have full 
responsibility and liability for any incorrect, incomplete, or omitted 
requirements and specifications, and any changes or additions to approved 
requirements or specifications shall be at Customer's expense.

     e. Prepare and input test data for and conduct acceptance testing of 
Software according to acceptance test plan as mutually agreed upon by the 
parties. If any such Software does not meet the acceptance test criteria, 
Customer shall notify IMSS in writing no later than thirty (30) days after the 
Customer's receipt of the Software, specifying which criteria are not met. IMSS 
shall, at its sole cost, correct the identified deficiencies, and





Page 5 of 12                                                    
<PAGE>
 
                                                         IMSS Services Agreement
--------------------------------------------------------------------------------

Customer shall have thirty (30) days after delivery of the corrected Software to
test the Software for the sole purpose of verifying that the deficiencies have 
been corrected and that the corrections have not introduced other deficiencies. 
If Customer fails to accept or reject any Software within the time period 
specified above, or instructs IMSS to use any Software in a production mode, the
Software shall be deemed accepted.

    f. Cooperate with IMSS generally, and in particular make available, as 
reasonably requested by IMSS, management decisions, personnel, information, 
approvals, and acceptances in order that the work of IMSS may be timely and 
properly accomplished.

    g. Provide IMSS with reasonable notification of, and lead time to respond 
to, service requests, including changes to the number or format of required 
output, study requests, and requests to modify the Software.

    i. Cooperate and assist IMSS in instructing Customer personnel to adhere to 
applicable IMSS security policies and standards as necessary to protect the 
information and assets of IMSS and its customers.


Article 6. Customer Protection


6.1 Customer Data
Customer Data provided to IMSS for processing under this Agreement shall be and 
remain the property of the Customer. Upon the expiration or termination of this 
Agreement for any reason such Customer Data shall be either erased from the 
data files by IMSS at its site or, if Customer so elects, returned to Customer 
by IMSS at IMSS expense. Customer Data shall not be used by IMSS for any purpose
other than for providing Services to Customer, nor shall such data or any part 
of such data be disclosed, sold, assigned, leased or otherwise disposed of to 
third parties by IMSS or commercially exploited by or on behalf of IMSS, its 
employees or agents.

6.2 Safeguarding Customer Data
IMSS will employ safeguards against the destruction, loss or alteration of the 
Customer Data in the possession of IMSS which are no less rigorous than those 
employed by IMSS to safeguard its own proprietary data.

6.3. Confidentiality
IMSS and Customer shall sign a mutual Confidentiality Agreement. This 
Confidentiality Agreement shall survive the expiration or termination of this 
Agreement for any reason.

6.4 Exclusivity of IMSS' Services
During the duration of this Agreement and any extension or renewal hereof, and 
for a period of two (2) years thereafter, IMSS agrees it will not perform 
services for or assign any employees of IMSS performing Services pursuant to 
this Agreement to perform any services of a similar nature for any person or 
entity in competition with Customer without the express written consent of the 
Customer. Customer agrees that such consent will not be unreasonably withheld.


Page 6 of 12                                                     
<PAGE>
 
                                                        IMSS Services Agreement
-------------------------------------------------------------------------------

Article 7. Payments to IMSS

7.1 Monthly Charges

Customer shall pay to IMSS the Monthly Charges set forth in a schedule to this
Agreement, plus the fees, costs and charges associated with any Special Services
performed by IMSS.

7.2 Special Services Charges

Customer shall pay IMSS for all additional Equipment, Third Party Software, and 
Special Services provided by IMSS in accordance with a payment schedule for such
items to be agreed upon in writing by the parties. If Customer requests IMSS to 
Modify any Software or if Customer requests that IMSS perform any new Software 
development or operation not included in this Agreement, IMSS shall advise 
Customer of the development, implementation and/or operating charges for those 
services, if any. Upon Customer's written approval of the Application 
Specifications and agreement to pay such charges, IMSS shall begin work. Any 
Modifications caused by any incorrect, incomplete or omitted specification or 
requirement of Customer-approved Application Specifications shall be paid for by
Customer at IMSS' then current rates.

7.3 Reruns

Customer shall pay the reasonable charges of IMSS for Reruns necessitated by 
incorrect or incomplete data or erroneous instructions supplied to IMSS by 
Customer.

7.4 Time and Manner of Payment

Customer will pay IMSS (i) the Monthly Charge, (ii) any one-time charges and 
(iii) charges for Special Services within thirty (30) days of the date of each 
invoice from IMSS for such charges. Invoices will be submitted to Customer no
sooner than the first day of the month after the month to which the invoiced
charges apply. Any sum due IMSS that is not paid within thirty (30) days of
receipt of the invoice shall accrue interest until paid at a rate of interest
equal to one percent (1%) per month. In the event any payment required under
this agreement or any of its schedules is tied to the successful completion of a
portion of the Services by IMSS and such completion has not been accomplished by
the scheduled payment/completion date, Customer may delay such payment until
there has been successful completion of such services without any interest
accruing.

7.5 Taxes, Travel and Living Expenses

Customer shall pay, or reimburse IMSS for payment of the actual travel and 
living expenses incurred in providing Services, any taxes or amounts paid in 
substitution or replacement of taxes, including privilege or excise taxes, 
however designated or levied, arising out of this Agreement.



Page 7 of 12  
<PAGE>
 

                                                         IMSS Services Agreement
--------------------------------------------------------------------------------

Article 8. Warranty and Maintenance

     a. IMSS warrants that it has full title and ownership of any Software that
it licenses to Customer and that it has full power and authority to grant any
such license(s). IMSS further warrants that Customer's use of the licensed
Software will not constitute an infringement or other violation of any
copyright, trade secret, trademark, patent or other proprietary right of any
third party. IMSS also warrants that, for one year after the commencement date
of any Software license agreement granted pursuant to this Agreement, the
licensed Software and Customized Software shall be free from any significant
programming errors and substantially free from defects in workmanship and
materials. THE WARRANTIES SET FORTH IN THIS SECTION ARE IN LIEU OF ALL OTHER
WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

     b. After the warranty period expires, Maintenance of the IMSS Software and
Customized Software and their costs to Customer shall be as specified in a
Schedule to this Agreement.

Article 9. Performance Review and Termination

9.1 Performance Review

The IMSS Account Manager and the Customer Project Manager will meet at least 
monthly, to review the performance of either party under this Agreement. In the 
event of any dispute or disagreement between the parties either in interpreting 
any provision of this Agreement or about the performance of either party, then 
upon the written request of either party, each of the parties will appoint a 
designated representative to resolve such dispute or disagreement. The 
designated representatives will discuss the problem and negotiate in good faith 
in an effort to resolve the dispute without any formal proceeding. During the 
course of such negotiation(s), all reasonable requests made by one party to the 
other for information, including copies of relevant documents, will be honored. 
The specific format for such discussions will be left to the discretion of the 
designated representatives. If the designated representatives are unable to 
resolve the dispute within thirty (30) days after their first meeting, each 
party will appoint a designated officer of its corporation to attempt to resolve
the dispute. No litigation for the resolution of such disputes may be commenced 
until the designated officers have met and either party has concluded in good 
faith that amicable resolution through continued negotiation does not appear 
likely (unless either party fails or refuses to schedule such a meeting of 
officers within a reasonable time after a request to do so by the other party).

9.2 Transition

In the event IMSS is unable to continue performing the Services required by this
Agreement because it ceases performing Services as contemplated by this 
Agreement, IMSS will give Customer as much advance notice of this

Page 8 of 12  
<PAGE>
 
                                                         IMSS Services Agreement
--------------------------------------------------------------------------------


inability as possible. Said notice shall specify the last date upon which IMSS
will be able to perform Services. This Agreement will terminate effective the
next business day after the date specified in said notice. After giving such
notice IMSS shall, if requested by Customer, cooperate with Customer in
achieving an orderly transition to another Service provider. For the sole
purposes of providing the same services to Customer as required of IMSS under
this Agreement, IMSS will, if so instructed by Customer, authorize such Service
provider to use all Software to which IMSS has granted such a license to
Customer and shall provide consulting and training Services to Customer and such
Service provider. If not in Customer's possession, IMSS shall provide a copy of
the source code and a limited use license for IMSS Software to Customer and its
new Service provider. IMSS shall also provide the source code for Customized
Software if it has not already done so. Compensation to IMSS for these Services
will be mutually agreed upon between IMSS and Customer through good faith
negotiations after IMSS has given the notice referred to above.

9.3 Termination for Cause

If either party materially or repeatedly defaults in the performance of any of
its duties or obligations under this Agreement (except for a default in payments
to IMSS, which is governed by Section 9.4 of this Agreement), which default is
not substantially cured within thirty (30) days after written notice is given to
the defaulting party specifying the default, or, with respect to those defaults
which cannot reasonably be cured within thirty (30) days, if the defaulting
party fails to proceed within thirty (30) days to commence curing said default
and to proceed with all due diligence to substantially cure the default, then
the party not in default may, by giving written notice of termination to the
defaulting party, terminate this Agreement as of a date specified in the notice
of termination.

9.4 Termination for Nonpayment

If Customer defaults in the payment when due of any amount owing to IMSS and 
does not, within thirty (30) days after being given written notice, cure such 
default, or, if Customer in good faith disputes an amount due, does not pay any 
undisputed amount and deposit the disputed amount into escrow in a major U.S. 
commercial bank to be designated by IMSS, with interest to be allocated to the 
party entitled to the principal upon resolution of the dispute, then IMSS may, 
by giving written notice to Customer, terminate this Agreement.

9.5 Rights Upon Termination

If IMSS terminates this Agreement for Customer's default, Customer shall
immediately pay IMSS for all Services performed and Software or Equipment
delivered through the termination date, plus reasonable termination costs,
including but not limited to (i) any losses incurred in connection with the
early termination of any lease or other agreement relating to services or
resources used by IMSS to perform the Services, (ii) any losses incurred in
connection with the sale of any resources then being used by IMSS in the
performance of the Services, and (iii) any other reasonable, documented costs
and expenses related to termination.

Page 9 of 12  
<PAGE>
 
                                                         IMSS Services Agreement
--------------------------------------------------------------------------------


Article 10. Remedies

10.1 Measure of Damages

The measure of damages recoverable from one party by the other for any reason,
whether arising by negligence, intended conduct or otherwise, shall not include
any amounts for indirect, special, consequential or punitive damages even if
such damages are foreseeable. Further, IMSS shall have no liability for damages
which could have been avoided had Customer exercised reasonable efforts to
verify the data furnished by IMSS before utilization of such data.

Article 11. Indemnities

11.1 Indemnity by Customer

Customer agrees to indemnify, defend and hold harmless IMSS and its officers,
directors, employees, agents, successors and assigns from any and all losses,
liabilities, damages, and claims (including taxes), and all related costs and
expenses (including reasonable attorneys fees) and costs of investigation,
litigation settlements, judgments, interest and penalties arising out of or in
connection with:

     a. The inaccuracy of any representations or warranties by Customer made
during the term of this Agreement;

     b. Any claims of infringement made against IMSS of any letters patent, or a
trade secret, or any copyright, trademark, service mark, trade name or similar
proprietary rights conferred by contract or by common law or by any law of the 
United States or any state, alleged to have occurred because of Software or 
other resources or items provided to IMSS by Customer;

     c. Customer's obligations pursuant to any agreements with third parties 
governing Customer Software or any other Customer resources utilized by IMSS in 
the performance of the Services;

     d. The failure by Customer to obtain any Required Consent.

11.2 Indemnity by IMSS

IMSS agrees to indemnify, defend and hold harmless Customer and its officers, 
directors, employees, agents, successors and assigns from any and all losses, 
liabilities, damages, and claims (including taxes), and all related costs and 
expenses (including reasonable attorneys fees) and costs of investigation, 
litigation settlements, judgments, interest and penalties arising from or in
connection with:

     a. The inaccuracy of any of the representations or warranties by IMSS made 
during the term of this Agreement;

     b. Any claims of infringement made against Customer for infringement of any
United States letters patent, or a trade secret, or any copyright, trademark, 
service mark, trade name or similar proprietary rights conferred by

Page 10 of 12                                              
<PAGE>
 
                                                         IMSS Services Agreement
--------------------------------------------------------------------------------

contract or by common law or by any law of the United States or any state, 
alleged to have occurred because of Software or other resources or items 
provided to Customer by IMSS.

11.3  Mutual Indemnity

IMSS and Customer each agree to indemnify, defend and hold harmless the other, 
its officers, directors, employees, agents, successors and assigns from any and 
all losses, liabilities, damages, and claims (including taxes), and all related 
costs and expenses (including reasonable attorneys fees) and costs of 
investigation, litigation settlements judgments, interest and penalties arising 
from or in connection with: (i) the death or bodily injury of any agent, 
employee, customer, business invitee or business visitor of the indemnitor; or 
(ii) the damage, loss or destruction of any real or tangible personal property 
in the possession or under the control of the indemnitor. The employees or 
agents of either party shall not, when at the premises of the other party, be 
deemed the other party's business invitee or business visitor.

Article 12. Miscellaneous

12.1  Binding Nature and Assignment

This Agreement shall bind the parties and their successors and permitted 
assigns. Neither party may assign this Agreement without the prior written 
consent of the other, which consent shall not be unreasonably withheld or 
delayed; provided that both IMSS and Customer shall have the right to assign 
this Agreement to any Parent, Affiliate, or Successors of IMSS or Customer 
without consent of the other party, and shall give at least sixty (60) days 
prior written notice of such assignment. Any assignment attempted without the 
written consent of the other party shall be void.

12.2  Notices

When one party is required or permitted to give notice to the other, such notice
shall be deemed given when delivered by hand or when mailed by United States 
mail, registered or certified mail, return-receipt requested, postage prepaid to
the parties at the addresses shown in the first paragraph of this Agreement.

12.3  Relationship of Parties

IMSS in furnishing services to Customer, is acting only as an independent 
contractor. Except where this Agreement expressly provides otherwise, IMSS does 
not undertake by this Agreement or otherwise to perform any obligation of 
Customer, whether regulatory or contractual, or to assume any responsibility for
Customer's business or operations. IMSS has the sole right and obligation to 
supervise, manage, contract, direct, procure, perform or cause to be performed, 
all work to be performed and resources used by IMSS under this Agreement, except
where it is specifically stated that Customer must give approval or consent.


Page 11 of 12    
<PAGE>
 
                                                         IMSS Services Agreement
--------------------------------------------------------------------------------

12.4  Force Majeure

Each party shall be excused from performance under this Agreement and shall have
no liability to the other party for any period it is prevented from performing 
any of its obligations (other than payment obligations), in whole or in part, as
a result of delays caused by the other party or by an act of God, war, civil 
disturbance, court order, labor dispute, third party performance or 
nonperformance, or other cause beyond its reasonable control, including failures
or fluctuations in electrical power, heat, light, Equipment, or 
telecommunications, and such nonperformance shall not be a default under, or 
grounds for termination of, this Agreement.

12.5  Attorney's Fees

If any legal action or other proceeding is brought for the enforcement of this 
Agreement, or because of an alleged dispute, breach, default or 
misrepresentation in connection with any of the provisions of this Agreement, 
the prevailing party shall be entitled to recover reasonable attorney's fees and
other costs incurred in that action or proceeding, in addition to any other 
relief to which it may be entitled.

12.6  Media Releases

All media releases, public announcements and public disclosures by Customer or 
IMSS relating to this Agreement or its subject matter, including promotional or 
marketing materials, shall be coordinated with and approved by the other party 
prior to release. This restriction does not apply to any announcement intended 
solely for internal distribution within Customer's or IMSS' organization.

12.7  Entire Agreement

This Agreement and all of its Attachments and Schedules constitute the entire 
Agreement between IMSS and Customer pertaining to the subject matter described 
herein.

IN WITNESS WHEREOF, IMSS and Customer have each caused this Agreement to be 
signed and delivered by its duly authorized representative.

INFORMATION MANAGEMENT SYSTEM              BLUE RHINO CORPORATION
SERVICES

Signature:   /s/ M. R. Martin              Signature:   /s/ Billy D. Prim
            ---------------------------                -------------------------

Typed Name:      Marvin R. Martin          Typed Name:      Billy D. Prim
            ---------------------------                -------------------------
          
Title:              President              Title:           Chairman & CEO
            ---------------------------                -------------------------

Date:               12/29/97               Date:               12/29/97
            ---------------------------                -------------------------


Page 12 of 12