EDIT: I have updated the post with a dump of nearly 290k unique results for JBIYH at 130,000 full keyspace walks.

We have collected almost 1M of unique results for LXACA.
This message is "special" because it is very short and hillclimb alone probably won't find the solution, there are lots of results with high scores and the actual solution might be hidden somewhere between them.
I passed the results found so far through a filter which tries to estimate the message readability. The files below contain all the unique results and also search results for some of the words that frequently appear in short messages, I'll update the list with more files later.

The format is: decoded text, readability score, hillclimb score

What we are looking for, is text that contains only full words with no garbles, or words separated by "x".

LXACA all results - over 20MB text file

LXACA MORGEN
LXACA TAGE
LXACA MELDUNG
LXACA FRAGE
LXACA FUNKE

JBIYH, format is the same as above: text, readability score (old algorithm), hillclimb score.

JBIYH all unique results

---

M4 Project homepage
M4 Project wiki

TJM pointed me to a program by j2kun. Using it and a dictionary from VE3NEA's repo I was able to get following results.

bachsteinderlandxein	-19.224825547743812	['bach', 'stein', 'der', 'land', 'x', 'ein']
wagenfelderxreinmars	-19.237768046711892	['wagen', 'felder', 'x', 'rein', 'mars']
xxschockxreinxmitten	-18.381848759133174	['x', 'x', 'schock', 'x', 'rein', 'x', 'mitten']
wunderaussiefortjens	-18.966607921369203	['wunder', 'aus', 'sie', 'fort', 'jens']
schneiderxschussxzug	-16.279945868754083	['schneider', 'x', 'schuss', 'x', 'zug']
xeinssiebefandenwird	-17.41155681739338	['x', 'eins', 'sie', 'befanden', 'wird']
xbeckervereindereins	-17.601556811841373	['x', 'becker', 'verein', 'der', 'eins']
xschlagenneinderkomm	-17.23161558153879	['x', 'schlagen', 'nein', 'der', 'komm']
fuenfrangmittellegtx	-18.396433602498796	['fuenf', 'rang', 'mittel', 'legt', 'x']
neinxfuerstanzennein	-18.974130447607543	['nein', 'x', 'fuers', 'tanzen', 'nein']
xhaltringvereinstand	-18.793672107604976	['x', 'halt', 'ring', 'verein', 'stand']
auslagesteinstandvom	-19.605666368920105	['aus', 'lage', 'stein', 'stand', 'vom']
xxschockxvierxschien	-18.6543058986985	['x', 'x', 'schock', 'x', 'vier', 'x', 'schien']
seinstrichneuenlagen	-17.443821738631836	['sein', 'strich', 'neuen', 'lagen']
dreiderzeugensattein	-19.0352127944047	['drei', 'der', 'zeugen', 'satt', 'ein']
xundsiebenxhartender	-17.494257869006677	['x', 'und', 'sieben', 'x', 'harten', 'der']
kchxmittxeinstellung	-19.003173807067895	['kchxmittx', 'einstellung']
pmitteinsatzwolltenx	-19.75918540250523	['pmitt', 'einsatz', 'wollten', 'x']
fuersiegestrichender	-14.677039694702135	['fuer', 'sie', 'gestrichen', 'der']
xmeldungxeinmitkiste	-18.26694377250403	['x', 'meldung', 'x', 'ein', 'mit', 'kiste']
bussprungvereingeste	-18.23192458221049	['bus', 'sprung', 'verein', 'geste']
kundereingrussausein	-19.77865854624187	['kunde', 'rein', 'gruss', 'aus', 'ein']
broemelderbewegungen	-19.533392111031564	['broemel', 'der', 'bewegungen']
xeinssteinsiegernull	-19.775246662273315	['x', 'eins', 'stein', 'sieger', 'null']
eunteinstreingesetzt	-19.759146601851974	['eunteinstr', 'eingesetzt']
ehrenstartxmitfuehre	-18.402274928833908	['ehren', 'start', 'x', 'mit', 'fuehre']
offenxeinssieseinman	-19.658956456415492	['offen', 'x', 'eins', 'sie', 'sein', 'man']
xgemeindereteinstein	-18.967318852063634	['x', 'gemeinde', 'ret', 'einstein']
sollnullstrandxfisch	-19.871307470011004	['soll', 'null', 'strand', 'x', 'fisch']
xgemeinderxheinstein	-18.967318852063634	['x', 'gemeinde', 'rxh', 'einstein']
klagestandxvierreinx	-19.611248049201766	['klage', 'stand', 'x', 'vier', 'rein', 'x']
felderxneungabwunder	-17.652479739340578	['felder', 'x', 'neun', 'gab', 'wunder']
keinmeinxbesteinssie	-19.502742189633366	['kein', 'mein', 'x', 'beste', 'ins', 'sie']
stundeneinsxvierxein	-18.63635402847329	['stunden', 'eins', 'x', 'vier', 'x', 'ein']
xfuerxbeiderxmasterx	-19.67904330331847	['x', 'fuer', 'x', 'beider', 'x', 'master', 'x']
kommeinfragenderlied	-18.794531202471546	['komm', 'ein', 'fragen', 'der', 'lied']
ysstagemeinteinstein	-19.90089758727919	['yssta', 'gemeint', 'einstein']
offenxkommenxzumdrin	-19.207385280071556	['offen', 'x', 'kommen', 'x', 'zum', 'drin']
trinssammeingetragen	-19.502183623769987	['trinssamm', 'eingetragen']
fbetriebestellenbeix	-19.683776888250197	['f', 'betriebe', 'stellen', 'bei', 'x']
apersoneneinxvereins	-19.366969801474816	['a', 'personen', 'ein', 'x', 'vereins']
xbestenxundxsteinman	-19.177235035447723	['x', 'besten', 'x', 'und', 'x', 'stein', 'man']

I selected only results with score better than -20.

I don't speak German but

stundeneinsxvierxein	-18.63635402847329	['stunden', 'eins', 'x', 'vier', 'x', 'ein']

makes the most sense to me.

Alex sent me a link to the mentioned program/algorithm and eventually it is going to be implemented on the server network for realtime/offline result analysis. The readability score next to the results posted above still uses the old algorithm.

---

M4 Project homepage
M4 Project wiki

According to this scoring algorithm there is no interesting segmentations of JBIYH.

Following are all results that yield at least 4 "words".

etinaqgsorrarjinungihrgannexkorsotevornzozwoffenxsorgte	-62.63721128638809	['etinaqgsorrarjinungihrgannexkorsotevornzozw', 'offen', 'x', 'sorgte']
ihrenxsiexoborttxkgetottanixvorfbrqxaqtaegmaarisuhaeine	-62.70126730705574	['ihren', 'x', 'sie', 'xoborttxkgetottanixvorfbrqxaqtaegmaarisuha', 'eine']
ihrenxsiexoburttxkgesottanixvordbruxaubaegmaarisqhaeine	-62.70126730705574	['ihren', 'x', 'sie', 'xoburttxkgesottanixvordbruxaubaegmaarisqha', 'eine']
mitsuchtesiegpunnfsetrodeslxwyseraurstantenxfleftzteasd	-62.745002580371704	['mit', 'suchte', 'sie', 'gpunnfsetrodeslxwyseraurstantenxfleftzteasd']
cxdahnoretmxotavxreumeixbtxduuegeahneturusfuehrtauchoel	-63.041812107735275	['cxdahnoretmxotavxreumeixbtxduuegeahneturus', 'fuehrt', 'auch', 'oel']
trotzihreinemxenhenueindljenxstxfefintonwjespaembmumget	-63.270078174903816	['trotz', 'ihr', 'eine', 'mxenhenueindljenxstxfefintonwjespaembmumget']
landxabersgxnereinaopwaszweistsineriquetrowxlungiaxmaqt	-63.56905937425903	['land', 'x', 'aber', 'sgxnereinaopwaszweistsineriquetrowxlungiaxmaqt']
eininsseieniexdrbittafxuzerertmtumerlazaromerkearsxnohc	-63.58027301046566	['ein', 'ins', 'seien', 'iexdrbittafxuzerertmtumerlazaromerkearsxnohc']
xaberkatzemevosaxurqfansnsxjgenzemmninsodengxverrefunng	-63.616997924020154	['x', 'aber', 'katze', 'mevosaxurqfansnsxjgenzemmninsodengxverrefunng']
jedexwernerxsqbxstrarerogendigegettlatlpermburdowxzsteq	-63.68827513499248	['jede', 'x', 'werner', 'xsqbxstrarerogendigegettlatlpermburdowxzsteq']
stufweginmdeihmxotekxmenstfarzeboludnagsoewagerfdiesiex	-63.75109478048915	['stufweginmdeihmxotekxmenstfarzeboludnagsoewagerf', 'die', 'sie', 'x']
xlassmittellegxezuesmeexjenstwaufzuuedtanskestrviehfxnn	-63.795553775135375	['x', 'lass', 'mittel', 'legxezuesmeexjenstwaufzuuedtanskestrviehfxnn']
xlassmittellegxezuexmeexjenstwaufzuuedtanskesorviehfxnn	-63.795553775135375	['x', 'lass', 'mittel', 'legxezuexmeexjenstwaufzuuedtanskesorviehfxnn']
waldbeidemvereinsuestdinlausmjaxdedieruenfrgwsvaneaubae	-63.800659689990106	['wald', 'bei', 'dem', 'vereins', 'uestdinlausmjaxdedieruenfrgwsvaneaubae']
derderaefeqmenfderjexsqusqemanxhhbaquaqtxetbitwockgnein	-63.805256696880704	['der', 'der', 'aefeqmenfderjexsqusqemanxhhbaquaqtxetbitwockgn', 'ein']
meindankedinolbzellnkxeizwshgehlebsmangekmxorbrustumehr	-63.935239888305546	['mein', 'danke', 'dinolbzellnkxeizwshgehlebsmangekmxorbrustu', 'mehr']
kheutxvejlarsxschintetdakltrijelxkdosteeitzyxsiediesgab	-63.95531959138182	['kheutxvejlarsxschintetdakltrijelxkdosteeitzyx', 'sie', 'dies', 'gab']
derqromxoefeuntfriellhetqubeiusneltwahrterdfnahlqessiex	-64.09226352493418	['der', 'qromxoefeuntfriellhetqubeiusneltwahrterdfnahlqes', 'sie', 'x']
szteqsxtskgegsltockxkerkfleaurzlistwonxlnkisepundersiex	-64.09226352493418	['szteqsxtskgegsltockxkerkfleaurzlistwonxlnkisepun', 'der', 'sie', 'x']
jfuenxekowhzugenesaqtexkexgeundzeanszftilevlxmoegenzurx	-64.09469189828035	['jfuenxekowhzugenesaqtexkexgeundzeanszftilevlx', 'moegen', 'zur', 'x']
hfxkaxgesdteausxtingytorsmebenvonpaelhenneinemxeineinex	-64.18702970678254	['hfxkaxgesdteausxtingytorsmebenvonpaelhenneinemx', 'ein', 'eine', 'x']
jfxhaxgeskrepolxtingstoqsmubenvonpaeljenneinemxeineinex	-64.18702970678254	['jfxhaxgeskrepolxtingstoqsmubenvonpaeljenneinemx', 'ein', 'eine', 'x']
dlxdveheimerpankdotxpreandovrefabhinzderxbtlovihremeinx	-64.23417125456092	['dlxdveheimerpankdotxpreandovrefabhinzderxbtlov', 'ihrem', 'ein', 'x']
hadocxreimerpankdotxpreandovrefashinzderxbtlovihremeinx	-64.23417125456092	['hadocxreimerpankdotxpreandovrefashinzderxbtlov', 'ihrem', 'ein', 'x']
tasixbirofxusgauwesssisumdlxkwkxensqosniskexzeundiexein	-64.27352420664805	['tasixbirofxusgauwesssisumdlxkwkxensqosniskexzeun', 'die', 'x', 'ein']
hisxwortendochtxhaepakerxfiibtenieltumaffaesirozkotterz	-64.27734587046503	['his', 'x', 'worten', 'doch', 'txhaepakerxfiibtenieltumaffaesirozkotterz']
wostesjexfuqxgudsisiheisjexbasslaunwaqtareicwerdetxmale	-64.27746874490224	['wostesjexfuqxgudsisiheisjexbasslaunwaqtareic', 'werdet', 'x', 'male']
junixdersileruelnatwagepansnexkzuaqtxinkchensqnnxktochx	-64.31380742256789	['juni', 'x', 'der', 'sileruelnatwagepansnexkzuaqtxinkchensqnnxktochx']
jdbefedpermbewespaeesxdiedekensedeartarbinfelixneuebeim	-64.3243997881057	['jdbefedpermbewespaeesxdiedekensedeartarbin', 'felix', 'neue', 'beim']
fhrekrirodnnftbettaetryttpeverschohlvoloshauvstauchxwas	-64.39156042625582	['fhrekrirodnnftbettaetryttpeverschohlvoloshauvst', 'auch', 'x', 'was']
xneuedochredantelsabrwurxdamidmaweixkordverstuensnzxhau	-64.39502591207854	['x', 'neue', 'doch', 'redantelsabrwurxdamidmaweixkordverstuensnzxhau']
xneundieishawaqerbesqxhwaxstorzelcbartensrelklantasonhe	-64.5099293884306	['x', 'neun', 'die', 'ishawaqerbesqxhwaxstorzelcbartensrelklantasonhe']
erbexkommennesstxotzissxvotmtpexsueqtnehmeaseitmenentrx	-64.54044936112565	['erbe', 'x', 'kommen', 'nesstxotzissxvotmtpexsueqtnehmeaseitmenentrx']
zweixsiermxgetibtreigkxnaeqbalegeekavditteererxwiehuqve	-64.56158630344075	['zwei', 'x', 'sie', 'rmxgetibtreigkxnaeqbalegeekavditteererxwiehuqve']
xaufdiezueqsujcfreittartmeenmastetroeivinizungunvxniseg	-64.57894241900614	['x', 'auf', 'die', 'zueqsujcfreittartmeenmastetroeivinizungunvxniseg']
xxdieqbatbjeldztxsodavgeztxeiggegefelgammeanibeszenitnv	-64.6169131041104	['x', 'x', 'die', 'qbatbjeldztxsodavgeztxeiggegefelgammeanibeszenitnv']
qxmtpaxuninitxhaffehxthungszindxrhennabeutrgnehoehexzur	-64.6337940555238	['qxmtpaxuninitxhaffehxthungszindxrhennabeutrgne', 'hoehe', 'x', 'zur']
einsksfaechendmixixjlgortsilmxtrastexqdeneinaqsteineure	-64.6456234258413	['ein', 'sksfaechendmixixjlgortsilmxtrastexqdeneinaq', 'stein', 'eure']
einsksfaechendxixixjlgortsilmxtrastexqdeieinaqsteineure	-64.6456234258413	['ein', 'sksfaechendxixixjlgortsilmxtrastexqdeieinaq', 'stein', 'eure']
aixaqusenmiinatsreiszsordamebeteuanffindoiqmaqassiexmit	-64.71176987242941	['aixaqusenmiinatsreiszsordamebeteuanffindoiqmaqas', 'sie', 'x', 'mit']
xtaqxaqsenidenbjigeerrmxchrafnaeqstzugenngungengelfeldx	-64.71854818997707	['xtaqxaqsenidenbjigeerrmxchrafnaeqstzugenngung', 'engel', 'feld', 'x']
xdorterdesoerinftlxemernsbeurfxunilstieletofxgezxnxklau	-64.7463968898649	['x', 'dort', 'erde', 'soerinftlxemernsbeurfxunilstieletofxgezxnxklau']
mbmxeikgxutzormxiqfetxwaxerlebillgeamlarzullxeinsiestar	-64.75009990876		['mbmxeikgxutzormxiqfetxwaxerlebillgeamlarzullx', 'ein', 'sie', 'star']
mitxderxefaefallxlakostztpiontaxxnhenxwoektonxuntxmetwa	-64.76815194183827	['mit', 'x', 'der', 'xefaefallxlakostztpiontaxxnhenxwoektonxuntxmetwa']
gseqstededrrmegleaqteeiqkorveerweswurtzteuerzlindermitx	-64.76815194183827	['gseqstededrrmegleaqteeiqkorveerweswurtzteuerzlin', 'der', 'mit', 'x']
ftoqeradeunabtqkomzindwadanfeldorteinsgadorchattsiexals	-64.77146253126135	['ftoqeradeunabtqkomzindwadanfeldorteinsgadorchatt', 'sie', 'x', 'als']
operxderderganbrofzweikfuehxlmemelertaeflerqfennfolromn	-64.78164000549471	['oper', 'x', 'der', 'der', 'ganbrofzweikfuehxlmemelertaeflerqfennfolromn']

In comparison to previous runs I adjusted one of variables in algorithm. I noticed that scores for "words" not present in dictionary were to high. That might lead algorithm to prefer random strings over words in dictionary for long words (>13 chars or so.) And long words aren't that unusual in German. To my disappointment it didn't change anything crucial - all scores ale lower by ~4 and no additional segmentations were found.