Yes, it is possible. The fact that we don't explore these options doesn't mean that they aren't possible. In fact, Canada does have a bilateral consular agreement with Egypt; it just doesn't happen to address detention issues.
It is not only possible, but I think it is the most effective way forward under international law. Some people have suggested that we should reopen the Vienna Convention on Consular Relations, for example. My response is that even the convention itself, in its final provisions, recognizes that any issues that are not adequately dealt with under the convention can be the subject of bilateral agreements.
I recently undertook a study of bilateral consular agreements, those that were adopted after the Vienna convention. I looked at I think 75 bilateral agreements, and almost all of them specified, what exactly do we mean by “consular access without delay”? What do we mean by “notification without delay”? What do we do about dual nationals? How do we address those concerns?
I think the bilateral consular mechanism is tailor-made for addressing these problems. That's not to say that every country would be willing, and that may well be something we need to work on diplomatically and politically. I do think that if Canada were to make it clear that it wants to resolve these problems through a time-honoured international legal mechanism, that's another card in our hand that at the present time we don't seem to be playing at all.