A recruiter for the Afghan jihad, or holy war, he became a suspect in the deadly Khobar Towers bombing because of his links to militant Islamics, including bin Laden.

It is believed he was also under suspicion over the 1995 bombing of the US National Guard headquarters in Riyadh, but has denied involvement in both attacks.

But Australia's Refugee Review Tribunal found he lied at least six times in his visa application, including using falsified documents, and was attempting to hide a violent history in Afghanistan.

"Although he sought to present himself as a man of peace, this does not sit well with his admitted strong support for the violent ideology of Osama bin Laden," tribunal member Dr Rory Hudson said in his September 30, 1998, findings.

"The only reasonable explanation would be the fact his activities in Afghanistan were not of a peaceful kind, but involved working with violent Islamic groups there, perhaps the Taliban or the Mujahedeen," Dr Hudson said.

"At the hearing, it appeared that he was trying to play down his connection to bin Laden as much as possible . . . it seems more likely, however, that that connection was closer than he has admitted."

Dr Hudson also believed the Palestinian was lying about why he became a suspect in the bombings.

After secretly arriving in Australia, he sought a protection visa in January 1997 but was rejected in June 1998 and again on review in September 1998.

He was previously denied visa applications in the US and Canada.

Immigration Minister Philip Ruddock's office said the man had been able to stay for so long because authorities were unable to get the appropriate documents to deport him.

"We are waiting on travel documents . . . a passport where he has right of residence," Mr Ruddock's spokesman, Steve Ingram, said.

The asylum seeker has admitted associations with the Al-Daawa group, banned in Saudi Arabia.

He claimed to have been beaten by Jordanian authorities in the late 1980s, was at one stage suicidal and had been approached to become a spy.

He admitted he was later recruiting youths in Afghanistan and publicising the holy war.

He said he met bin Laden twice, at a meeting in Saudi Arabia and again in Afghanistan in 1991.

He also claimed to have met Afghan leader Sheik Abdulla Azzam at least three times before being unable to meet again because Azzam was "always away fighting".

Azzam was killed in a bomb blast in Pakistan in 1989.

The asylum seeker had spent time studying computers in Germany, a country where multiple arrests were made last week in connection to the New York and Washington terrorist strikes.

He told the tribunal he believed he remained under surveillance by Saudi authorities after his arrival in Australia and said a man he met at a local mosque attempted to search his belongings.

Evidence before the tribunal suggested the man's wife and two children have remained in Saudi Arabia enduring poverty and persecution since his arrival in Australia in October 1996.

Sources said Australian security authorities had investigated the man. The outcome of that investigation remains unknown.

Mr Ingram said the tribunal had found the man to be "stateless", which had complicated attempts to return him overseas.

But Mr Ingram said there were no urgent moves to have him deported despite the US massacres of September 11 and pending strikes in Afghanistan.

"We are aware of the seriousness of the situation but to suggest we are blithely ignoring someone who is a terrorist is wrong," Mr Ingram said. "Issues of security are something we take very seriously.

"In terms of some of the radical groups in the Middle East, they do have thousands if not hundreds of thousands of followers, but not all of those would be prepared to be involved in terrorist activities."

Mr Ingram said some protection visa applicants were known to claim being arrested or investigated by overseas authorities to bolster a case of persecution.

Many countries in the Middle East and northern Africa routinely detained people in such circumstances, he said.

"It could be that it is a police state they are in and they round up anybody, that is not uncommon. But it doesn't make them criminal and it doesn't make them not criminal."