Here is version 1.0 of the completed macro.  If I can get it to run faster
or more cleanly, I'll post the update too.  Cheers!

Sub ReplaceInSlides()
   '
****************************************************************************
   ' Version: 1.0, Date: 13.Dec.2005
   ' This macro will perform a search-and-replace within the bodies of
PowerPoint
   ' slides that have been pasted into a Word document.  This macro should
be run
   ' from within the Word document, not the PowerPoint presentation.  The
macro
   ' will pop up dialog boxes asking for the text to be found and the text
to
   ' replace it with.  PowerPoint must be installed locally too, and slides
will
   ' be temporarily opened in PowerPoint as they are edited from the Word
doc.
   ' The macro is unavoidably very slow.  Don't interact with PowerPoint or
Word
   ' while the macro is running.
   '
****************************************************************************
   Dim strFind, strReplaceWith, strMessage, strTitle As String
   Dim intCount, i As Integer

   Dim objPPT As PowerPoint.Application
   Dim objSlide As PowerPoint.Slide
   Dim objShape As PowerPoint.Shape
   Dim objTextRange, objTextRangeFound As PowerPoint.TextRange

   strMessage = "Enter the text you wish to find in the slides pasted into
this Word document and have replaced with something else.  (Make sure to
back up your Word document first.  Close any currently-open PowerPoint
slides.)"
   strTitle = "Find What?"
   strFind = InputBox(strMessage, strTitle)

   strMessage = "Now enter what you wish to replace that text with."
   strTitle = "Replace With?"
   strReplaceWith = InputBox(strMessage, strTitle)

   intCount = ActiveDocument.InlineShapes.Count

   If intCount > 0 Then
       Set objPPT = New PowerPoint.Application
       objPPT.Visible = True

       For i = 1 To intCount
           If Left(ActiveDocument.InlineShapes.Item(i).OLEFormat.ProgID,
16) = "PowerPoint.Slide" Then
               ActiveDocument.InlineShapes(i).OLEFormat.DoVerb
wdOLEVerbOpen

               Set objSlide = objPPT.ActivePresentation.Slides(1)

               For Each objShape In objSlide.Shapes
                   If objShape.HasTextFrame Then
                       Set objTextRange = objShape.TextFrame.TextRange
                       Set objTextRangeFound =
objTextRange.Replace(FindWhat:=strFind, Replacewhat:=strReplaceWith,
WholeWords:=False)

                       Do While Not objTextRangeFound Is Nothing
                           Set objTextRange =
objTextRange.Characters(objTextRangeFound.Start + objTextRangeFound.Length,
objTextRange.Length)
                           Set objTextRangeFound =
objTextRange.Replace(FindWhat:=strFind, Replacewhat:=strReplaceWith,
WholeWords:=False)
                       Loop
                   End If
               Next objShape

               'Saving is required to force changes to be saved to the Word
doc.
               'This is why the macro runs so slowly...
               ActiveDocument.Save

               objPPT.ActivePresentation.Saved = True
               objPPT.ActivePresentation.Close
           End If
       Next

       objPPT.Quit

   Else
       MsgBox "Could not find any slides in the Word document."
   End If

End Sub