> ループだと期待通り「ノード0」が得られますが、
> 再帰だと「ノード3」が返却されます。

Return された戻り値を捨てているからですね。

ループ版では、「temp = 別のノード」に相当する代入式がありますが、
再帰版にはそれが無いので、「Dim temp As TreeNode = node」のままになっているわけです。