Now the letter of guarantee is not enough!
I crossed the border at Gallabat - Metema two days ago and they said that the law has changed just two days ago: Now you need a confirmation from the foreign ministry of Ethiopia. Me and some other overlanders were stuck in the border but they let us through the next day. I still don't know what happened and whether the law has really changed or not but just a heads up for anyone crossing the border - it might take a while.
I was in contact with my ambassador but I don't no whether it helped or not. If the law has really changed, it could be that in the future they don't let people through that easily.