How to Delete Order Item from Order Object in Magento

in Mage_Adminhtml_Model_Session_Quote ->getOrder() is not a magic method, but a real method exists in the class:

/**
 * Retrieve order model object
 *
 * @return Mage_Sales_Model_Order
 */
public function getOrder()
{
    if (is_null($this->_order)) {
        $this->_order = Mage::getModel('sales/order');
        if ($this->getOrderId()) {
            $this->_order->load($this->getOrderId());
        }
    }
    return $this->_order;
}

From the logic above, is is apparent why you are getting a null'd order Object.

What you need to do is simply store the OrderId into the session object. When you call for getOrder(), it will then populate the order correctly in the result. See code in getOrder() method.

Thus use:

Mage::getSingleton('adminhtml/session_quote')->setOrderId($orderId);

When things don't work as expected, go have a look at the class that you are using.

Not all methods are magic methods in magento, sometimes a method can be a magic method in once class, and not in another. (one of the features that can make magento code both confusing, and powerful to extend)

As stated in the comments the script you have should work nicely for magento version 1.4+.
In the 1.4 version the sales entities were mapped to flat tables that have constraints so everything should cascade nicely.

For versions prior to 1.4 all the entities related to sales (orders, invoices, shipments and creditmemos) were EAV and kept in the same tables. So nothing cascade.
For version prior to 1.4 you can try this script.
This should work for later versions also but I don't think it's needed.

$orders = Mage::getModel('sales/order')->getCollection()
    ->addFieldToFilter('entity_id', (array) $orderIds);
foreach ($orders as $o) {
    //load order object - I know it's not ok to use load in a loop but it should be ok since it's a one time script
    $order = Mage::getModel('sales/order')->load($o->getId());

    $invoices = $order->getInvoiceCollection();
    foreach ($invoices as $invoice){
        //delete all invoice items
        $items = $invoice->getAllItems(); 
        foreach ($items as $item) {
            $item->delete();
        }
        //delete invoice
        $invoice->delete();
    }
    $creditnotes = $order->getCreditmemosCollection();
    foreach ($creditnotes as $creditnote){
        //delete all creditnote items
        $items = $creditnote->getAllItems(); 
        foreach ($items as $item) {
            $item->delete();
        }
        //delete credit note
        $creditnote->delete();
    }
    $shipments = $order->getShipmentsCollection();
    foreach ($shipments as $shipment){
        //delete all shipment items
        $items = $shipment->getAllItems(); 
        foreach ($items as $item) {
            $item->delete();
        }
        //delete shipment
        $shipment->delete();
    }
    //delete all order items
    $items = $order->getAllItems(); 
    foreach ($items as $item) {
        $item->delete();
    }
    //delete payment - not sure about this one
    $order->getPayment()->delete();
    //delete quote - this can be skipped
    if ($order->getQuote()) {
        foreach ($order->getQuote()->getAllItems() as $item) {
            $item->delete();
        }
        $order->getQuote()->delete();
    }
    //delete order
    $order->delete();
}