Stop Button

Where possible, I'd avoid Application.DoEvents which (as here) can produce unexpected behaviour.

As the code in the RunStep() method will execute very quickly, a BackgroundWorker or multi-threading is not very suitable either.

What I'd suggest you do instead is to use a timer with a short interval, say 60 milliseconds. This doesn't use much in the way of resources and all the code will continue to execute on the user interface thread

So, I'd add a timer to your form, double click on it to add a Tick handler and change your code as follows:

Public Class Form1

    ' Run Button
    Private Sub RunButton_Click(sender As System.Object, e As System.EventArgs) Handles RunButton.Click
        Label1.Text = "RUNNING"
        Timer1.Interval = 60
        Timer1.Start()
    End Sub

    ' Stop Button
    Private Sub StopButton_Click(sender As System.Object, e As System.EventArgs) Handles StopButton.Click
        ' should now get called on first click
        Timer1.Stop()
        Label1.Text = "STOPPED"
    End Sub

    Public Sub RunStep()
        Dim ValueHolder As Integer

        ' Process some data
        For i = 1 To 79
            For j = 1 To 79
                ValueHolder = i * j + 23
            Next
        Next  
    End Sub

    Private Sub Timer1_Tick(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Timer1.Tick
        RunStep()
    End Sub

End Class