The widow's pension offers a little information that may help track down his regiment. Attached is the file where Sallie notes that his regiment was a member of McNair's Brigade and was commanded by a Captain C.M. Ohlson (Olsen?).
I would post a query here
http://www.history-sites.com/cgi-bin/bbs62x/mscwmb/webbbs_co...asking if anyone can identify the regiment given the name of the Captain and the brigade in which it may have served at some time. Mention, too, that he lived in Lauderdale County in 1860.
The only McNair that comes to mind is Evander McNair whose brigade was active in the Vicksburg siege in 1863. I know his command usually had Arkansas regiments and am not sure if any from Mississippi were attached or not.
As far as I know, an exchanged Confederate soldier would have been one that was surrendered and then allowed to return to service after having been exchanged for a Union soldier. I believe those surrendered at Fort Donelson were later exchanged, and know that those captured at Vicksburg were, but understand that the practice was later discontinued.
Try posting your query at that board. Those folks tend to know a good bit and can probably help track down this regiment.
Good luck,
Scott