Well I'am super paranoid but I guess you already know that ,
Being a paranoid may do some good to you but being a super paranoid won't.
I'am even paranoid to make Paper wallet and after the years I found out that the Public key & the private key don't match
Public key can be derived from private key. So you only need to backup your private keys. What you said is not "plausible" unless if there is any mistyping/mistakes on your part when backing up. To check if you have done it right, you can just import private key and see if the private key you imported matches with the private key you exported.
If you are still not satisfied, you can backup a few wallet softwares which you can use if something like this ever happens.
No. They can not crack Electrum seeds. Brainwallet crackers stole Bitcoins from weak brainwallets. They can not crack very randomly generated brainwallets.
You are mistaken between a brainwallet, a seed and brainwallet.org. Although a brainwallet and a seed are similar, all three are three different. A brainwallet is a passphrase which can be byhearted easily and to memorize easily, people usually use easy passphrases such as abcde12345, which is very easy to crack. Whereas, a seed is randomly generated data. Obviously, randomness will be high for computer generated data than human's. However, combining both will give a much better result.
P.S. See
https://bitcointalk.org/index.php?topic=311000.msg3345309#msg3345309.
Because if that software use Brainwallet.org and they run locally and offline as you said they could access Electrum if they got the seed
Electrum does not use Brainwallet.org. Electrum is a Bitcoin wallet and Brainwallet.org is a website which offers a variety of tools.
You are able to recover Bitcoin from seeds using Brainwallet.org because it has a tool which can be used to recover Bitcoins from a seed.
P.S. Also read,
https://rya.nc/cracking_cryptocurrency_brainwallets.pdf.
* Edited.