A mobile wireless communications device may include an antenna, and a receiver coupled to the antenna and being configured to use a modulation having memory for a received message in a block structure. The block structure may include a pair of mini-probes and a body therebetween. The receiver may be configured to demodulate the received message by determining a corresponding set of received signal characteristic values based upon the pair of mini-probes, and determining a decode starting point in the body based upon the set of received signal characteristic values. The receiver may be configured to demodulate the received message by at least, from the decode starting point, decoding the body in a first time direction, and decoding the body in a second time direction based upon a result of the decoding in the first direction.