락프리 스택 Push 코드 중에서

node 포인터는 스택에 존재하지만, new Node 부분은 계속 힙에서 메모리 할당 받는 거 아닌가요?

네 맞습니다.

그럼 다른 스레드가 접근할 때마다 메모리를 계속 할당 받을텐데, 해제를 안하면 나중엔 결국 문제가 되는 거 아닌지.

여기서 말하는건 [메모리 해제] 관련된 문제가 아니라,
다른 쓰레드가 동일한 힙 주소에 접근해서
멋대로 해제하거나 조작할 수 없다는 것입니다.
당연히 그 어느 누군가도 해제를 안 하면 메모리 누수로 인해 언젠간 터지겠죠.