Intra-operative quality assurance and dosimetry optimization in prostate brachytherapy critically depends on the ability of discerning the locations of implanted seeds. Various methods exist for seed matching and reconstruction from multiple segmented C-arm images. Unfortunately, using three or more images makes the problem NP-hard, i.e. no polynomial-time algorithm can provably compute the complete matching. Typically, a statistical analysis of performance is considered sufficient. Hence it is of utmost importance to exploit all the available information in order to minimize the matching and reconstruction errors. Current algorithms use only the information about seed centers, disregarding the information about the orientations and length of seeds. While the latter has little dosimetric impact, it can positively contribute to improving seed matching rate and 3D implant reconstruction accuracy. It can also become critical information when hidden and spuriously segmented seeds need to be matched, where reliable and generic methods are not yet available. Expecting orientation information to be useful in reconstructing large and dense implants, we have developed a method which incorporates seed orientation information into our previously proposed reconstruction algorithm (MARSHAL). Simulation study shows that under normal segmentation errors, when considering seed orientations, implants of 80 to 140 seeds with the density of 2.0- 3.0 seeds/cc give an average matching rate >97% using three-image matching. It is higher than the matching rate of about 96% when considering only seed positions. This means that the information of seed orientations appears to be a valuable additive to fluoroscopy-based brachytherapy implant reconstruction.