Hi Vardan

you can create a new delivery for that sales order from Warehouse and send back to your client

if your delivery is cancelled then it will not affect in your inventory so go on and create new delivery... While in invoice there should not any problem as you said it has been paid so just create a new delivery and use no need to worry about that

for your information . OpenERP provide invoice differently

Thanks
Sandeep