A powerful watchdog could be asked to force British ministers to give more details of what they know about America flying terror suspects via the UK.
Suspected rendition flight in Prague, April 2005
The Lib Dems say they will complain to the parliamentary ombudsman if they are not given details of flights passing through British military bases.
Ministers say it would be too costly to give the information.
It comes as figures show two planes suspected of being used to carry suspects crossed UK airspace 200 times.
UK ministers say the US has only made two requests to transport suspects via the UK - both in the 1990s.
Foreign Secretary Jack Straw has said there is no record of President George W Bush's administration asking for British airspace or territory to be used for such flights - called renditions.
On Wedneday, he told reporters: "We know of no occasion where there has been a rendition through United Kingdom territory or indeed over United Kingdom territory, nor do we have any reason to believe that such flights have taken place without our knowledge."
Human rights campaigners claim the flights are being used to fly suspects to countries where they can be tortured.
But US Secretary of State Condoleezza Rice has said suspects are flown abroad for interrogation - a process called rendition.
But she has denied that torture is used.
Lib Dem foreign affairs spokesman Sir Menzies Campbell asked the Ministry of Defence about two planes, one of which had changed its registration number twice.
The planes have featured in media reports about claims that suspects are being flown to third countries for torture.
Sir Menzies wanted to know how many times the planes had used UK military bases en route to or from countries like Jordan, Syria, Uzbekistan or Egypt.
But Defence Minister Adam Ingram said in a written parliamentary answer: "The information requested is not recorded centrally and could be provided only at a disproportionate cost."
It is understood there is a £650 limit on the cost of answering parliamentary questions.
The Lib Dems say that is not good enough when allegations of complicity with torture are involved.
A party spokesman said Lib Dems had written to Mr Ingram warning it would complain to the watchdog if the government did not ask the separate military bases for the information.
"Unless they conduct inquiries at that level, we will take this to the parliamentary ombudsman," said the spokesman.
'What did UK know?'
National Air Traffic Services (Nats) have confirmed the planes have flown over Britain.
Nats told the Lib Dems it could not specify the number of flights but now it has told Channel 4 News the planes had made about 200 flights in the past five years.
Lib Dem foreign affairs spokesman Nick Clegg said: "Frankly that flies in the face of the answer we received from the Government that only two or three cases of rendition ever took place."
He said the latest twist meant prompted new questions.
"We don't have the answers yet and the most important issue that needs to be clarified now is what does the British Government know about what these CIA flights are up to," he said.
But a Ministry of Defence spokeswoman said: "We have not approved and will not approve a policy of facilitating the transfer of individuals through the UK to places where there are substantial grounds to believe they would face a real risk of torture."
MPs on the Commons foreign affairs committee are on Thursday due to given their preliminary findings on the flights' claims when they publish their latest human rights report.
The committee's chairman, Labour MP Mike Gapes, said: "The bottom line is that we have not had the full story, the full facts.
"My select committee has been pursuing this for some time and gradually, bit by bit, we get more and more pieces of the jigsaw but we haven't got the whole picture yet."