I finally got to the bottom of my problem. Looks like I used the wrong Enumeration:

Source.SetProperty("format", New GLib.Value(Gst.Constants.TIME_FORMAT))

It turns out that Gst.Constants.TIME_FORMAT is actually a time format string. What I needed was:

Source.SetProperty("format", New GLib.Value(3)) ' TimeFormat

This works regardless of whether I set a timestamp on the buffers I pass to the appsrc.