I would use a way of tagging each of the border shapes when I put them in. That way it is much easier to identify the borders and kill them off. The normal (cheats

) way I go about tagging a shape is to use its alternative text property and hope that none of your other shapes has used the same thing. An example of doing it this way is...
Code:
Sub AddRandomBorder()
Dim aRng As Range, i As Integer, aPara As Paragraph, aShp As Shape
Dim iWidth As Integer, iHeight As Integer
With ActiveDocument.Sections(1).PageSetup
iWidth = .PageWidth - 40
iHeight = .PageHeight - 40
End With
'Get rid of the existing borders
For i = ActiveDocument.Shapes.Count To 1 Step -1
If ActiveDocument.Shapes(i).AlternativeText = "Page Border" Then ActiveDocument.Shapes(i).Delete
Next i
For Each aPara In ActiveDocument.Paragraphs
Set aRng = aPara.Range
aRng.Collapse Direction:=wdCollapseStart
If aRng.Information(wdActiveEndPageNumber) > i Then
Set aShp = ActiveDocument.Shapes.AddShape(Type:=1, Left:=20, Top:=20, _
Width:=iWidth, Height:=iHeight, Anchor:=aRng)
With aShp
.AlternativeText = "Page Border"
.Line.ForeColor = RGB(Rnd() * 255, Rnd() * 255, Rnd() * 255)
.Line.Weight = 3
.Fill.Transparency = 1
End With
i = aRng.Information(wdActiveEndPageNumber)
End If
Next aPara
End Sub