Coulson dömdes på tisdag för konspiration att hacka telefoner. Goodman hade redan erkänt sig skyldig 2006.
Men jurymedlemmar kunde inte besluta om anklagelser mot paret av konspiration att begå fel i offentliga ämbeten.
Domaren kritiserade David Cameron för att han kommenterade fallet medan juryn fortfarande överlade.
Under tiden har BBC fått veta att ett av offren var Carole Middleton, hertiginnan av Cambridges mamma.
På tisdagen bad premiärministern om ursäkt för att anställa Coulson som sin kommunikationschef men att han hade gjort det "på grundval av åtaganden jag gavs av honom om telefonhackning och dessa visade sig inte vara fallet."
Coulsons advokat kritiserade Camerons "tillrådda och förhastade ingripande" i fallet - ett drag som beskrevs som "ovis" av f.d. lordkansler Ken Clarke.
Domaren kommenterade: "Jag anser att det som har hänt är otillfredsställande när det gäller rättvisa och rättsstatsprincipen."
Herr domare Saunders sa att ett beslut om en ny rättegång skulle fattas på måndag.
Fem personer har erkänt sig skyldiga i fallet, medan före detta chefsdirektör Rebekah Brooks och hennes man Charlie var bland de återstående svarande som godkändes på tisdag.
David Cameron kritiserades av Labourledaren Ed Miliband för premiärministerns frågor för sitt beslut att ta Coulson med sig till Downing Street.
Labour vill ha en utredning av varför Coulson inte fick den högsta nivån av säkerhetsprövning när han gick med i Nej. Tio operationer.
Men Cameron insisterade på att det hade varit statsförvaltningens uppgift att granska utnämningen och att han hade rentvåts genom en offentlig utredning efter hackningsskandalen.
"Varje en av dessa frågor behandlades uttömmande av Leveson undersökning," den främsta gruvarbetare berättade MPs.
"Han tittade på alla dessa frågor om de varningar jag fick och svaret jag gav och han kritiserade inte mitt uppförande."
BBC: s Robert Peston sade att, om det skulle bli en utredning, skulle det vara chef för statsförvaltningen, Sir Jeremy Heywood, inför förlägenhet över misslyckandet med att veterinär Coulson.
Men Miliband räknade upp en rad anklagelser om statsministerns roll och insisterade: "När det gällde Andy Coulson ville du inte veta bevisen.
"Detta handlar om din karaktär, ditt omdöme och de varningar du ignorerade."
Cameron utnämnde Coulson till sin officiella talesman efter att ha blivit premiärminister 2010, endast för den tidigare News of the World redaktör att avgå 2011 mitt i växande anklagelser om telefon hacking på tidningen.
Premiärministern hade blivit "den förste som någonsin tagit sitt kontor som förde en brottsling in i hjärtat av Downing Street", tillade Miliband.
Telefonhackande domar i sin helhet:
Clive Goodman - Nyheterna från världens tidigare kungliga redaktör - och privatdetektiv Glenn Mulcaire har redan avtjänat fängelsestraff.
2007 dömdes de efter att ha hackat mobilerna till medlemmar av det kungliga hushållet.
Royals, kändisar och offer för brott fick sina telefoner hackas av den nu defungerade tabloid, som stängde i juli 2011 efter avslöjanden om mördade skolflicka Milly Dowler röstmeddelanden som kom fram.
Polisen säger att tusentals människors telefoner var riktade.
Andra offer för hackning, som inte nämndes under rättegången, inkluderade grevinnan Wessex och hertiginnan i York.
År 2006, när hacking på tabloid först avslöjades, polisen etablerade att 19 medlemmar av det kungliga hushållet eller deras nära medarbetare fick sina meddelanden lyssnade på olagligt.
I kölvattnet av domsluten uppmanade Millys syster Gemma premiärministern att uppfylla sitt löfte att göra "verkliga permanenta förändringar" på det sätt som pressen regleras.
Efter att juryn avskedats sade biträdande kommissionär Cressida Dick att Met hade varit "medvetet om de sensibiliteter och juridiska komplexiteter som finns i att undersöka en nationell tidning".
Kraften hade kritiserats för sitt förhållande till News International och för att inte fullfölja anklagelser om hackning 2006.
Men Dick - som övervakade utredningen - sade: " Under hela utredningen har vi gjort vårt bästa för att följa bevisen, utan rädsla eller ynnest.
– Denna utredning har aldrig handlat om ett angrepp på pressfriheten utan om att fastställa om några brott hade begåtts, att fastställa vem som var ansvarig för att ha begått dem och att ställa dem inför rätta. Offren förtjänade inte mindre."
Coulson står nu inför högst två års fängelse för hackning.
Han och fru Brooks hade en on-off-affär i minst sex år från slutet av 1990-talet, vars detaljer avslöjades under rättegången.
Fru Brooks anklagades för att hämta lådor - med hjälp av sin assistent Ms Carter - från News International-arkivet som gällde hennes tid som redaktör för Nyheterna om världen och solen.
Hon anklagades också, tillsammans med sin man och herr Hanna, för att dölja persondatorer för polisen.
Fem andra personer har redan erkänt sig skyldiga till relaterade anklagelser om konspiration till hacka telefoner.
Mulcaire, en privatdetektiv, före detta nyhetsredaktörer Greg Miskiw och James Weatherup och reportrar Dan Evans och Neville Thurlbeck hade tidigare erkänt sin roll i handlingen för att få berättelser genom att avlyssna röstmeddelanden.
Medan vissa rapporter har satt rättegångskostnaden på upp till 100 miljoner pund, HM Courts och Tribunal Service sade att det var omöjligt att beräkna eftersom det inte föra fall per ärende.
Crown Prosecution Service sade att dess kostnader enbart var 1,7 miljoner pund - varav 1,2 miljoner pund spenderades på advokatarvoden.
En jury har misslyckats med att komma fram till domslut om två ouppklarade anklagelser mot före detta nyhetsredaktören Andy Coulson och journalisten Clive Goodman.