Вам понадобится объект таймера, чтобы запускать код каждые X минут. Использовать отдельный поток для проверки веб-службы необходимо только в том случае, если проверка займет некоторое время, и вы хотите, чтобы ваша форма оставалась отзывчивой в течение этого времени.
Использовать таймер очень просто:
Private WithEvents timer As New System.Timers.Timer
Private Sub Form1_Load(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Load
'Set interval to 1 minute
timer.Interval = 60000
'Synchronize with current form, or else an error will occur when trying to
'update the UI from within the elapsed event
timer.SynchronizingObject = Me
End Sub
Private Sub timer_Elapsed(ByVal sender As Object, ByVal e As System.Timers.ElapsedEventArgs) Handles timer.Elapsed
'Add code here to check if the web service is updated and update label
End Sub