- Gaining a border (or being a nation with a capital in the same continent) helps. Conquering nearby nations to gain a little border may be worth your time, especially if your opponents don't border it. Keeping enemies from bordering it also would help, but is probably trickier.
- Technology can help.
- Good relations with Egypt can help (at least in AHD, iirc).
- Rebellions can be really helpful, but aside from war there's not much you can really do to destabilize Egypt.
- Don't gain too much influence too quickly. You don't want to be the biggest target for everyone to ban/discredit/decrease influence/expel - you want to always be the second biggest target, or even less of a target. Don't disturb the status quo too much. Gain influence slowly, especially if another nation is getting close to having enough influence to decrease influence or ban (you may even want to stop influencing Egypt at all when they get close). They'll choose to use their influence on stopping some other rival if you're behaving yourself - then, when they're drained, you can continue to build up your influence.
- I've seen suggestions before to try to quickly gain influence in another state they are trying to influence, forcing a response from them there (thus making them have to devote more attention to those states because of the loss of points they used discrediting or banning you).
It still won't be easy, though.