I consulted Heinrich Heine: Sämtliche Werke. Düsseldorfer Ausgabe, in 16 volumes, published by Hoffmann und Campe in the 1990s. The register of titles and first lines (in volume 16) does not list "Frühlingsbotschaft", but it does list the first line "Leise zieht durch mein Gemüth".
The poem starting with the line "Leise zieht durch mein Gemüt" is poem VI of Neuer Frühling, which was included in the Neue Gedichte, published by Hoffmann und Campe in 1844. So you could find the poem via the wikisource page that was referenced in the question.
In the Düsseldorfer Ausgabe, the poem is on page 14 of volume 2 (Neue Gedichte). According to the notes and comments (page 350f), the poem was probably written between the winter of 1830/1831 and May 1831. The poem may have had a third stanza, which was apparently dropped.
Since the text is in the public domain by now, you can find the entire text below:
Leise zieht durch mein Gemüth
Klinge, kleines Frühlingslied,
Kling’ hinaus in’s Weite.
Kling’ hinaus, bis an das Haus,
Wo die Blumen sprießen.
Wenn du eine Rose schaust,
Sag’ ich lass’ sie grüßen.