How works something like this: If shp("Subtitle").Visible = False Then
Does it mean that there is no shape Subtitle on slide or there is shape Subtitle on slide but with visibility turned off in Selection Pane?
It means that visibility is turned off - but the shape still exists.

Is there way to check if shape DO NOT EXIST on slide? I mean as a condition?
If there is no shp("Subtitle") on slide Then ?
Yes. You can use this function to find a shape with a particular name (as in the name you see in the selection pane):

Public Function getShapeByName(shapeName As String, slSlide As Slide) As Shape
  Dim s As Shape
  For Each s In slSlide.Shapes
    If s.Name = shapeName Then
      Set getShapeByName = s
      Exit Function
    End If
  Next
  Set getShapeByName = Nothing
End Function
and check whether or not the return is nothing. For example:

Public Sub ShapeTest()


  Dim myShape As Shape
  Dim mySlide As Slide
  Set mySlide = Application.ActiveWindow.View.Slide


  Set myShape = getShapeByName("Rectangle 3", mySlide)


  If myShape Is Nothing Then
    MsgBox "No shape found"
  Else
    MsgBox "Shape found"
  End If


End Sub