A Bitcoin Generator Scam (BGS) is a type of cyberattack in which scammers promise to provide individuals with free cryptocurrencies if they pay a mining fee. Although graph neural networks (GNNs) have been used for detecting other cryptocurrency frauds, the usefulness of these methods for BGS detection has not been studied. In this paper, we carry out extensive experiments to assess the use of both standard machine learning (ML) methods and GNNs to detect Bitcoin transactions associated with activities stemming from Bitcoin Generator Scams. We observe that the over-smoothing problem exists in GNNs designed for BGS detection and show that Random Walk Positional Encoding (RWPE) allows representing long-range interactions between far-away transactions in GNNs without causing over-smoothing. We show that the General, Powerful, Scalable (GPS) Graph Transformer with RWPE outperforms both GNN and ML based state-of-the-art fraud detection methods in Bitcoin Generator Scams. We also analyze the effectiveness of Breadth First Search (BFS) for graph sampling and show that it should not be used as it induces bias toward the subnetwork structure. We propose the Random First Search (RFS) sampling alternative and show that this is a more suitable solution.