Referential integrity issue with Untyped XML in TS

I am going to start off by displaying my table structures:

Numbers Table:

Id  AccountId  MobileNr    FirstName  LastName    AttributeKeyValues  Labels
--- ---------- ----------- ---------- ----------- ------------------- -------
490 2000046    2XXXXXXXXXX Eon        du Plessis  <attrs />           <lbls>
                                                                        <lbl>Meep11e</lbl>
                                                                        <lbl>43210</lbl>
                                                                        <lbl>1234</lbl>
                                                                        <lbl>Label 5</lbl>
                                                                        <lbl>Label 6 (edit)</lbl>
                                                                      </lbls>
-----------------------------------------------------------------------------

Labels Table:

Id          AccountId   Label             RGB    LastAssigned            LastMessage
----------- ----------- ----------------- ------ ----------------------- ------------
91          2000046     Meep11e           000000 2013-04-15 13:42:06.660 NULL
-------------------------------------------------------------------------------------

This is the issue

Every number can have multiple labels assigned to it and is stored as untyped XML. In Numbers.Labels //lbls/lbl/text() you will notice that the text there will match the text in Labels.Label

This is the stored procedure which updates the Numbers.Labels column, and is run by an external application I am busy writing. The XML structure is generated by this external application, depending on which rows are read in the Labels.Label table

CREATE PROCEDURE [dbo].[UpdateLabels]
    @Id     INT,
    @Labels XML
AS
BEGIN
    UPDATE 
        Numbers
    SET
        Labels = @Labels
    WHERE
        Id = @Id

    UPDATE 
        Labels
    SET
        LastAssigned = GETDATE()
    WHERE
        label
    IN
        (SELECT @Labels.value('(//lbls/lbl)[1]', 'VARCHAR(100)'))
    END

The issue here is if 2 people log onto the same account, both with their own session, and User 1 tries to run this update stored procedure, but just before the button is pressed to do this update, user 2 deletes 1 of the labels in the Labels.label table which was included in User 1's update session, it will cause the XML to include the "Deleted" row, and can be problematic when I try to query the numbers again (The RGB column gets queried when I display the number since the label is marked up in jQuery to have a hexidecimal colored background)

My thought approach went to checking if the rows included in the built up XML exists before committing the update. How can I achieve this in TSQL? Or can any better way be recommended?

EDIT

Our table structure is intentionally denormalized, there are no foreign key constraints.

EDIT 2

Ok, it would seem my question is a bit hard, or that I brained too hard and got the dumb :). I will try and simplify.

In the Labels column in Numbers, every <lbl> element must exist within the Labels table
When updating the Labels column in Numbers, if a Label in the XML is found which does not exist in the Labels table, an error must be raised.
The XML is pre-formed in my application, meaning, every time the update is run, the old XML in the Labels column in Numbers will be REPLACED with the new XML generated by my application
This is where I need to check whether there are label nodes in my XML which no longer exists within the Labels table

I would check to see if there are rows in your xml that are not in the real table (in the database) before trying anything. And if you find something, exit out early.

Here is a Northwind example.

Use Northwind
GO

DECLARE @data XML;

SET @data = 

N'
<root>
    <Order>
        <OrderId>10248</OrderId>
        <CustomerId>VINET</CustomerId>
    </Order>
    <Order>
        <OrderId>-9999</OrderId>
        <CustomerId>CHOPS</CustomerId>
    </Order>
</root>';


/* select * from dbo.Orders */

declare @Holder table ( OrderId int, CustomerId nchar(5) )

Insert Into @Holder (OrderId , CustomerId )
SELECT
      T.myAlias.value('(./OrderId)[1]', 'int') AS OrderId
    , T.myAlias.value('(./CustomerId)[1]', 'nchar(5)') AS CustomerId
FROM 
    @data.nodes('//root/Order') AS T(myAlias);


if exists (select null from @Holder h where not exists (select null from dbo.Orders realTable where realTable.OrderID = h.OrderId )) 
BEGIN
    print 'you have rows in your xml that are not in the real table.  raise an error here'
END
Else
BEGIN
    print 'Using the data'
    Update dbo.Orders Set CustomerID = h.CustomerId
    From dbo.Orders o , @Holder h
    Where o.OrderID = h.OrderId
END