Unable to Delete Line Items From Sales Order

If users remove Items from a Sales Order and receive the warning "Items on this line item have been fulfilled. If you wish to delete the line, you must first delete the corresponding line(s) in the associated transaction(s).", consider if the Show Unfulfilled Items On Invoices  on Setup > Accounting > Accounting Preferences > Order Management tab is enabled.

With the above setting enabled, the unfulfilled Items are displayed/listed on the Invoice. That being the case, the Items must first be delisted from the Invoice. To delist, perform the following:

1. On the same Sales Order, navigate to the Related Records tab > Related Records sublist.
2. Click on linked Invoice.
3. Click Edit.
4. Remove the related Items.
5. Click Save.