WiMAX is a broadband internet access standard for both a fixed and mobile wireless networks. In WiMAX, base stations (BSs) with beamforming capability do not announce beamforming weights explicitly. Instead, weights are applied to pilot subcarriers in units of major groups. Shorter packets such as voice over IP (VoIP) packets do not span a full major group creating the problem of multiple users in the same major group using the same beamforming weights. This paper proposes a multi-user beamforming solution with user pairing for a practical WiMAX BS. A criterion for pairing users and an efficient tree-search algorithm is proposed with a complexity suitable for implementation. Furthermore, closed form results for a line-of-sight (LOS) channel are presented providing insight into the problem. Finally, performance results from a WiMAX VoIP scenario show that the performance with paired users using the same weights only is 0.5dB off single user beamforming results and providing a large gain over a standard cyclic-delay-diversity (CDD) beamforming strategy.