Attaching additional items to an order that has already been fulfilled/paid

We have a scenario in our business where new items can be added to a Sales Order after the order's original items have been marked as fulfilled. Additionally, the Sales Order will almost certainly have a Cash Sale already applied to it.

Is it possible via the web service to append new, unfulfilled items to a sales order that already contains fulfilled items? I don't want to remove the previously fulfilled items, just add the new unfulfilled items. These new items are zero-priced service items. Even though they are not adding additional costs to the order, we still want to track their sales for reporting purposes. Creating a new sales order is not a viable option.