I investigate the scalability of distributed virtual environments (DVEs) based on a structured peer-to-peer (P2P) overlay. I focus on network load and message routing latency. To this end, I study a prototypical DVE consisting of a simple game scenario and a P2P architecture based on Pastry and Scribe as proposed by Knutsson et al. The overall network load per host and the message routing latency in my simulation grow logarithmically with the number of hosts. I analyze the reason for the logarithmic scaling behavior of the network load. I expect this is to be primarily due to the network load being constant except for the overhead messages incurred by the overlay protocol, which is confirmed both by my theoretical analysis and simulation results. Furthermore, the network load incurred by using Pastry scales logarithmically with the number of hosts. The message routing latency, primarily caused by the employed routing protocol, scales the same way as Pastry, i.e. logarithmically with the number of hosts. Knutsson et al.’s results are in partial contradiction to mine. I propose a solution to this contradiction.