They have nowhere else to go.

They were born in the part of the former Soviet Union that is now Ukraine, but aren't citizens of that country.

"Ukraine doesn't want us, " says Oleg, 46. "If immigration puts us on a plane, Ukraine won't accept us.

We've no documents to enter.

We want to stay here."

It's a story that closely resembles the plot of Steven Spielberg's film, The Terminal, but this is no fairy story.

Oleg and Elena came to Ireland five years ago, living in Dublin before moving to Belfast. They lost their claim for asylum and last week were evicted from the Ark hostel in sub-zero weather.

Their £10 a day subsidy from the National Asylum Support Services was also withdrawn.

It was snowing when they arrived at the offices of SDLP MP Alasdair McDonnell looking for help.

"I was appalled, " McDonnell says. "Last year, a young Ukrainian woman, Oksana Sukhanova, became homeless. She suffered severe frostbite after sleeping rough in freezing weather. Her legs had to be amputated. There was a huge public outcry but nothing has changed. Every government agency I've contacted has denied having a duty of care to ensure Oleg and Elena don't freeze to death on the streets. The system is a failure."

The couple were saved only when landlord Declan Boyle heard of their plight and offered them a vacant house for three weeks. "We don't know where we'll go after that but we have hope to the end, " says Oleg.

Their lack of Ukrainian citizenship means immigration services have nowhere to deport them to. An official from the Immigration Directorate in Liverpool is expected to travel to Belfast to interview them on St Patrick's Day.

Les Allamby of the Refugee Action Group says: "For the fourth-largest economy in the world to treat people like this is a modern-day scandal."

"They're trying to starve us out. We have nothing but I won't beg. Only shameless people do that. Money isn't everything. My treasure is Elena, " says Oleg, hugging his wife.

They're living in a tiny upstairs bedroom to save electricity. "We need only a small heater and a 40-watt bulb for light. Elena makes a good Russian soup. One bowl does all day."

They have biscuits and coffee too, which they drink from blue and orange mugs of smiling, winking faces.

They sleep in a single bed.

"Elena would like a bigger bed but in this I can feel her close to me, " says Oleg. The Red Cross gave them pillows. The bedspread is their own. "See the tiger on it, " says Elena, pointing proudly at the pattern. "It's my animal. It protects us." A Russian Orthodox picture of the Virgin Mary hangs above the bed.

Oleg became an unregistered citizen in 1980 when he absconded to avoid conscription: "I didn't want to fight in Afghanistan. I wasn't involved in politics but I didn't agree with invading another country."

The vastness of the USSR meant he could evade authorities, working as a labourer in Siberia and Russia.

"When the Soviet Union broke up and Ukraine got independence, I was still worried I was in trouble. I was never registered in Ukraine so I have no status. I am a nobody."

He met Elena, 45, also drifting and unregistered, when they were both receiving help from the Helsinki Commission for Human Rights in Moscow.

"My baby Vladimir died in 1987. My husband was killed fighting in Afghanistan two years later. I'd left home to find work in Russia and was never registered in Ukraine, " she says.

"We support each other, " says Oleg. "I play the guitar for Elena. She makes me food and keeps me calm."

In 2000, they travelled illegally to Iceland. "I thought we'd be welcome because it's so cold that few immigrants go there, " Oleg says.

They applied for residency but then heard about Ireland . . . "a beautiful, green country where the people show their emotions". They entered Dublin illegally in 2001.

"We weren't claiming persecution but were told applying for asylum was the only way of staying." They withdrew their claim when advised it could take up to four years to process.

They then travelled north and reported to Newry police station: "We were arrested and put in Maghaberry prison for 12 days. We were told claiming asylum was the only way to get out."

With their application refused but nowhere to deport them to, they live in limbo. "We want to stay in Belfast and maybe work in a park with flowers and trees, " says Oleg. "We want a house of our own and neighbours who know we are good people and say 'Oleg and Elena, hey, how are you?'" Oleg picks up his guitar and plays. "The song is 'Na Malenkom Plotu'. I sang it to Elena when we met . . . 'I will take you on my raft through the storm. We will leave everything behind except our dreams'."