A fully coherent acceleration search algorithm has been applied to the Parkes multibeam pulsar survey of the Galactic plane to search for previously undiscovered relativistic binary pulsars. The search has resulted in the discovery of 16 pulsars including a binary millisecond pulsar and an intermittent pulsar. Despite a number of promising candidates there have been no new discoveries of relativistic binary pulsars. Here, we detail the acceleration search performed in our analysis and present coherent timing solutions for each of the pulsars discovered. In light of the lack of discoveries of relativistic binary pulsars, we also discuss the technique of acceleration searching and its effectiveness in finding these systems. © 2013 The Authors. Published by Oxford University Press on behalf of the Royal Astronomical Society.