The men who detained him were Pakistanis working for the Bahraini security services which are run by a former British colonial policeman, Ian Henderson. A Bahraini was thus prevented from entering Bahrain and deported from Bahrain by foreigners. Kafka has nothing on this.
Nor is Mr Birali's fate uncommon. Around 100 Bahrainis - along with wives and children - have been unceremoniously bundled out of their own country over the past three years, en route for Doha, Dubai, London, Damascus and Tehran, all for the crime of demanding a return to the 1973 constitution and the dissolved 1975 parliament.
Officially accused of conspiracy to overthrow Sheikh Issa bin Salman al-Khalifa's State of Bahrain or of "links to terrorist movements", the exiled Bahrainis languish in cramped apartments, pleading with their embassies to renew their passports in order to maintain citizenship of a country to which they cannot return. Almost all of them blame Mr Henderson, who controls the Bahrain Special Intelligence Service (SIS), for their plight.
"I went back to Bahrain in March 1993 and they arrested me in the immigration queue," Mr Birali says. "They were Pakistanis, and one of them asked: 'Why did you come here?' I said: 'This is my country.' Then they took my passport and told the crew of the Yemeni plane I'd arrived on that they must take me back to Sanaa, claiming I was a Palestinian. The police denied I'd arrived on a Bahraini passport. But I'd photocopied my passport and when the Yemeni pilot realised the policemen were lying, he wouldn't let me back on board. So the Bahrain police took me away with a friend who'd arrived on the same plane, both of us blindfolded, to a locked room near the airport. Then they took off my blindfold and took my photograph.
"In the room, my friend and I were separated. A guard was with me, four feet away from me, day and night. Towards the end, a police sergeant came in with an envelope and said: 'You want something to read? Try this!' It was a report on my life in Bahrain, written in English, from 1957 till that very day, about 30 pages of it.
"Then a Bahraini called al-Maowda came in and said: 'I have a message from Henderson who says you cannot come back to Bahrain without permission. If you come back to Bahrain, we have the report you've just read which contains confessions which implicate you. We can put you in prison now under the State Security Law.' I told al-Maowda I'd done nothing wrong - that all I'd done was demand the return of the Bahraini constitution and the parliament."
Instead, Mr Birali was held in his locked room for seven days and put on a flight back to Yemen. "They took us straight to the boarding gate at Bahrain airport. The officer who arrested us a week before handed me a brand new Bahraini passport valid for five countries - Yemen, Lebanon, Syria, Jordan and Iraq - and gave me a ticket to Sanaa." Mr Birali holds out his passport. It contains the photograph taken of him by the police in the sealed airport room. "Issued 13/4/1993," it says. "Expires 13/4/94. Born: 1938. Occupation: Employee. Abdulla [sic] Ali Rashed al-Birali. Nationality: Bahraini."
In 1994, Mr Birali waited three months in Damascus for the Bahraini embassy to extend the validity of his passport. In despair, he flew back to Bahrain again, this time on a flight of Gulf Air, Bahrain's national airline. "All my family were waiting to see me, but again I was taken to the locked room. The following morning, they extended my passport and put me back on the flight to Damascus. I didn't see my family." Last year, when he applied at the Bahraini embassy in Damascus yet again for a passport extension, they granted his request - on condition he did not go home.
Not that Mr Birali expected much else. The British threw him out of Bahrain twice - in 1960 and 1967 - after he had joined a local nationalist movement calling for the end of British colonial rule in the Middle East and helped form the National Liberation Front of Bahrain. In 1969 he again returned, this time with his Lebanese wife and baby daughter. Ten days later, he was arrested and imprisoned for 18 months for alleged involvement in a car bomb attack against a British policeman. He says he had no knowledge of the bombing. On his release, he was deported to Lebanon.
When the British left Bahrain in 1971, Mr Birali returned for post-independence national elections. He failed to gain a seat. "Then in 1974 the Saudis became very nervous. They didn't want our democracy on their doorstep. The Saudi and Bahraini foreign ministers met on 18 June and six days later I and most of the members of the Bahraini Liberation Front were arrested and sent to prison."
He was released in 1975 and again ordered into exile. "Before I left, I tried through mediation to stay at home. I wrote a letter to Sheikh Issa, to his son and brother, to all the governments in the Gulf, asking for help. I received no answer to any of these letters. The authorities said I might be able to stay if I signed a document admitting 'anti-government activities'. I refused."