Weird behavior with PROGMEM and escaped chars

You can put a space between '\x86' and 'aa'; don't know if it suites you. What is 'aa' supposed to be; part of the 'replacement string' or text? I suspect the latter.

By the way, if you're worried about flash memory usage, why do you seem to piss away flash memory by using fixed width strings and only use part of this fixed width (in your example)? It's probably a fine balance, but usually one stores single (not: an array of) strings in PROGMEM and next stores an array of pointers to those strings; this array can be in RAM or PROGMEM. If you have lots of short strings and only a few long ones, it pays of.