After a lot of faffing about, solution turned out to be rather simple; all I had to do was to check whether the field is empty or not before executing the code body of on_change function, here's a little example:

def onchange_item1(self, cr, uid, id, item1_id=None, context=None):
    domain = {}
    value = {}

    if item1_id:
        #Clear all selections
        value = {'item2_id': False,}

    return {'domain': domain,
            'value': value}

def onchange_item2(self, cr, uid, id, item2_id=None, context=None):
    domain = {}
    value = {}

    if item2_id:
        #Clear all selections
        value = {'item1_id': False}

    return {'domain': domain,
            'value': value}