Randomize (encrypted) data to hide the behaviour of the data source
I assume that you meant to xor the message with the LSFR state, and not with the fixed key.

Even in that case, one problem that you don't cover is that if the attacker knows/guesses that the data between two different exchanges is the same, he can recover the LSFR state (and from that, he gets everything).

What he would do is xor the two ciphertexts $LFSR^k \oplus P$ and $LFSR^{k+n} \oplus P$; that gives him $LFSR^k \oplus LFSR^{k+n}$; if he knows how large $n$ is (the number of times you cycled the LFSR between the two messages), then recovering the original LFSR state is a simple exercise in linear algebra.

Designing such a system really isn't a task for amateurs; it's far too easy to come up with a system with subtle vulnerabilites such as above.  Instead, I would suggest you use a system designed by an expert.

I was going to write some advice here about how to sketch out such a system; however I realized that I don't know enough about your system constraints and required security model to do it justice.  However, someone needs to do it, and you're not the right person.

I'm not criticizing you; actually, your list of requirements ("the messages need to be randomized", "no security by obscurity", "no reliable timesync", "message loss may happen") shows you've thought about it.  It's just that making an efficient and secure encryption system is a lot harder than it looks.

As for some of the constraints that would need to be considered by an expert:


You mention potential evesdroppers; do you also need to worry about someone modifying the ciphertext (perhaps in hope of making predictable changes in the decrypted data)?
How large can the ciphertexts be?
You said that you had constraints in both time and memory; how tight are those constraints?  Is the memory constaints on program size or data size?  If you're on a CPU, is that an 8-bit CPU, or a 32-bit CPU?
If someone recovers the key somehow, they can read all the data; are you OK with that?