Do you mean purified proteins from e.coli? or e.coli protein pellet prior protein purification?
Generally the pellets to be subjected to protein purification are quite stable and can be stored direclty at -20°C for months or years.
Storage of purified protein is more sensitive to the intrinsic protein properties, therefore, some trials in small scale need to be performed before find out the best condition.
Generally many proteins can be frozen at uM concentrations (1-100uM) with out addition of glicerol. However in some cases strong precipitation can be observed under frozen in this condition and the addition of 15-20% of glicerol is needed to prevent this precipiation.
I suggest to you to perform at least 3 cicle of froze/thawwith out glicerol (using dry ice or storing the samples at -20°C - 100ul of sample in eppendorf is enough). After 3 cycle of froze/taw you centrifuge the sample at high speed, collect the surnatant and compare (by SDS page o by protein quantification by bradford or BCA assays) the original and the final sample to see if protien concentration is reduced.
Generally if your protein samples are concentrated in the order of mg/ml in case that the protein precipitate, you will clearly see wthite precipitate formation.
liofilization is a possible alternative, but to liofilize a protein you need to remove or drastically reduce the salt contained in the buffer prior liofilizzation and not all the proteins are stable in this condition.
Most of the time, soluble proteins can be flash-frozen, stored at -80oC, and shipped on dry ice. In some cases, it is acceptable to store the protein at -20oC in 50% glycerol, and ship it on wet ice. I wouldn't recommend lyophilization unless you test it first. Many proteins require stabilizers such as trehalose to survive lyophilization. Lyophilized protein should be stored at -20oC.
Am comment for shipping on dry ice: Make sure your tubes are air-tight closed as the CO2 from the dry ice tends to get solved in your respective storage buffer which can lead to a significant acidification and, consequently, harm your protein when buffer capacity is used up. There are even papers out about that.