Das Bundesgericht stellt fest und zieht in Erwägung:
1. Der aus dem Kosovo stammende X._ (geb. 1971) reiste 1999 illegal in die Schweiz ein. Nachdem sein Asylgesuch abgewiesen worden war, heiratete er am 18. Februar 2002 die Schweizer Bürgerin Z._ (geb. 1947) und erhielt in der Folge eine Aufenthaltsbewilligung zum Verbleib bei ihr. X._ wurde in der Schweiz wiederholt straffällig. So verurteilte ihn etwa das Berner Obergericht am 12. September 2006 zweitinstanzlich zu einer Freiheitsstrafe von 26 Monaten (unbedingt) u.a. wegen mehrfachen banden- und gewerbsmässigen Diebstahls, mehrfachen Hausfriedensbruchs sowie wegen Gewalt und Drohung gegen Behörden und Beamte. Nachdem er im vorzeitigen Strafvollzug zunächst wegen aggressiven Verhaltens für sechs Monate in die Sicherheitsabteilung hatte verlegt werden müssen, wurde er rückwirkend auf den 24. Januar 2006 bedingt entlassen.
Mit Verfügung vom 6. März 2007 lehnte es der Migrationsdienst des Kantons Bern ab, die Aufenthaltsbewilligung von X._ zu verlängern und wies diesen gestützt auf Art.10 Abs. 1 lit. a ANAG für unbestimmte Zeit aus der Schweiz aus. Am 5. April 2007 erhob X._, vertreten durch Fürsprecher Guy Ehrler, gegen diese Verfügung Beschwerde bei der Polizei- und Militärdirektion des Kantons Bern. Das Verfahren vor dieser Instanz ist zur Zeit hängig.
Am 31. Januar 2008 verurteilte das Bezirksgericht Zürich X._ u.a. wegen mehrfacher Drohung, versuchter Nötigung und versuchter Anstiftung zur Falschaussage zu einer unbedingten Gesamtfreiheitsstrafe von 20 Monaten. X._ meldete hiegegen Berufung an (so dass das genannte Urteil heute noch nicht in Rechtskraft erwachsen ist), verbüsste aber auch diese Strafe im vorzeitigen Strafvollzug; mit Verfügung des Bezirksgerichts Zürich vom 3. April 2008 wurde er daraus entlassen und am 21. April 2008 dem Migrationsdienst des Kantons Bern zugeführt, der gegen ihn am 11. April 2008 Ausschaffungshaft angeordnet hatte. Auf der entsprechenden Haftanordnung war vermerkt, dass X._ durch Fürsprecher Guy Ehrler vertreten werde, was von diesem mit Schreiben vom 9. April 2008 mitgeteilt worden war. Mit Verfügung vom 21. April 2008 setzte das Haftgericht III Bern-Mittelland den Haftprüfungstermin auf den folgenden Tag an, ohne diese Verfügung dem betreffenden Rechtsvertreter zu eröffnen, und es führte die mündliche Verhandlung am 22. April 2008 ohne dessen Anwesenheit durch. Mit Entscheid vom selben Tag genehmigte es die Ausschaffungshaft bis zum 19. Juli 2008.
2. Mit Eingabe vom 2. Mai 2008 führt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, den Entscheid des Haftgerichts III Bern-Mittelland vom 22. April 2008 aufzuheben (Ziff. 1) und ihn - den Beschwerdeführer - aus der Ausschaffungshaft zu entlassen (Ziff. 2). Gleichzeitig wird um unentgeltliche Rechtspflege und Verbeiständung ersucht.
Das Haftgericht III Bern-Mittelland hat unter Hinweis auf den angefochtenen Entscheid auf Vernehmlassung verzichtet und beantragt, die Beschwerde abzuweisen. Der Migrationsdienst des Kantons Bern hat sich nicht vernehmen lassen. Das Bundesamt für Migration verzichtete ebenfalls auf eine Stellungnahme. Mit Eingabe vom 16. Mai 2008 hat sich der Beschwerdeführer noch einmal geäussert.
3. Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, so kann die zuständige Behörde den betroffenen Ausländer zur Sicherstellung des Vollzugs u.a. dann in Ausschaffungshaft nehmen bzw. in dieser belassen, wenn er andere. Personen ernsthaft bedroht oder an Leib und Leben erheblich gefährdet und deshalb strafrechtlich verfolgt wird oder verurteilt worden ist (Art. 76 Abs. 1 lit. b Ziff. 1 in Verbindung mit Art. 75 Abs. 1 lit. g AuG), oder wenn konkrete Anzeichen befürchten lassen, dass er sich der Ausschaffung entziehen will (Untertauchensgefahr, Art. 76 Abs. 1 Ziff. 3 AuG). Die Haft darf höchstens drei Monate dauern; stehen dem Vollzug der Weg- oder Ausweisung besondere Hindernisse entgegen, so kann sie mit Zustimmung der kantonalen richterlichen Behörde für volljährige Personen um höchstens 15 Monate verlängert werden (Art. 76 Abs. 3 AuG). Die für den Vollzug der Weg- oder Ausweisung notwendigen Vorkehren sind umgehend zu treffen (Beschleunigungsgebot, Art. 76 Abs. 4 AuG); die Haft wird u.a. beendet, wenn der Haftgrund entfällt oder sich erweist, dass der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar ist (Art. 80 Abs. 6 lit. a AuG). Die Verhafteten können mit ihren Rechtsvertretern mündlich und schriftlich verkehren (Art. 81 Abs. 1 Satz 2 AuG). Sodann ist die Haft in geeigneten Räumlichkeiten zu vollziehen (Art. 81 Abs. 2 Satz 1 AuG).
4. 4.1 Der Beschwerdeführer macht im Wesentlichen geltend, weil das Haftgericht Fürsprecher Guy Ehrler nicht zum Haftprüfungsverfahren vorgeladen habe, sei sein Anspruch auf rechtliches Gehör verletzt. Sodann bestreitet er das Vorliegen eines Haftgrundes und macht geltend, im Falle der Entlassung aus der Ausschaffungshaft gefährde er die öffentliche Ordnung und Sicherheit nicht; auch bestünden keine Anhaltspunkte, dass er sich den Ausländerbehörden entziehen würde. Seine Frau nähme ihn jederzeit bei sich auf. Schliesslich wendet er ein, die Ausweisung lasse sich innert nützlicher Frist gar nicht vollziehen: Er habe gegen die Ausweisungsverfügung Beschwerde eingereicht, über welche noch nicht entschieden worden sei (wobei der spätere Entscheid gegebenenfalls noch beim Verwaltungsgericht des Kantons Bern angefochten werden könne). Die Aufrechterhaltung der Ausschaffungshaft erweise sich daher als unverhältnismässig.
4.2 Der erste Einwand des Beschwerdeführers erscheint offensichtlich begründet: Indem die Haftrichterin die Haftverhandlung ohne den vom Betroffenen mandatierten Rechtsvertreter durchführte, verletzte sie dessen Anspruch auf rechtliches Gehör (<ref-law>, vgl. Urteil 2A.236/2002 vom 27. Mai 2002, E. 3, in Pra 2002 Nr. 142 S. 769). Zwar hat der Beschwerdeführer an der Verhandlung vor der Haftrichterin gegen die Abwesenheit seines Vertreters nicht protestiert; entscheidend ist jedoch, dass die Vorladung zu dieser Verhandlung nicht auch an den Rechtsvertreter zugestellt wurde, welcher gegebenenfalls auf seiner Anwesenheit an der Verhandlung beharrt bzw. den Beschwerdeführer entsprechend beraten hätte. Die Beschwerde ist in diesem Punkt begründet und der angefochtene Entscheid deshalb aufzuheben.
4.3 Nicht jede Verletzung von Verfahrensvorschriften bei der Haftprüfung führt indessen auch zur Haftentlassung. Es kommt darauf an, welche Bedeutung einerseits den verletzten Vorschriften für die Wahrung der Rechte des Betroffenen und andererseits dem Interesse an einer reibungslosen Durchsetzung der Ausschaffung zukommt. Wenn etwa der Ausländer die öffentliche Sicherheit gefährden könnte, besteht die Sanktion allein in einer Wiederholung der Haftrichterverhandlung unter Beizug des gewählten Rechtsvertreters (<ref-ruling> E. 3a S. 158 mit Hinweisen, Urteile 2A.296/1996 vom 24. Juni 1996, E. 4, und 2A.236/2002 vom 27. Mai 2002, E. 4.1 und 4.2). Voraussetzung für die Aufrechterhaltung der Haft ist in jedem Falle, dass sich den Akten zumindest gewisse Hinweise für das Vorliegen eines Haftgrundes entnehmen lassen (<ref-ruling> E. 2 S. 114/115).
4.4 Die genannten Voraussetzungen treffen hier zu: Allein schon der Umstand, dass der Beschwerdeführer während der Verbüssung seiner ersten Freiheitsstrafe für sechs Monate in die Sicherheitsabteilung der entsprechenden Strafanstalt verlegt werden musste, zeigt, dass er über hohes aggressives Potential verfügt. Nur kurze Zeit nach der Entlassung aus dem Strafvollzug hat er erneut schwer delinquiert: Zwar hat er gegen das entsprechende Urteil des Bezirksgerichts Zürich vom 31. Januar 2008, in welchem er u.a. wegen Drohungen zu einer weiteren Freiheitsstrafe von 20 Monaten verurteilt worden ist, Berufung eingelegt, doch ergibt sich bereits aus den im vorliegenden Verfahren von ihm selber eingereichten Akten, dass er laut den Polizeiprotokollen den Versand von so genannten "Droh-SMS" eingestanden hat (vgl. S. 3 der Ausweisungsverfügung vom 6. März 2007). Es bestehen nach dem Gesagten gewichtige Indizien, dass vom Beschwerdeführer eine erhebliche Gefahr für andere Personen ausgeht und diesfalls der Haftgrund von Art. 75 Abs. 1 lit. g AuG erfüllt erscheint. Das öffentliche Interesse an einer Aufrechterhaltung der Ausschaffungshaft besteht damit fort.
4.5 Auch der Einwand, mit dem Vollzug der Ausweisung könne nicht innert nützlicher Frist gerechnet werden, was gemäss Art. 80 Abs. 6 AuG zur Beendigung der Haft führen müsse und diese als unverhältnismässig erscheinen lasse, ist unbegründet: Zwar versteht sich nicht von selbst, dass der Vollzug der Ausweisung innert der für die Dauer der Ausschaffungshaft zulässigen Frist durchführbar bleibt, wenn - wie hier - der erstinstanzliche Beschwerdeentscheid über die genannte fremdenpolizeiliche Sanktion noch aussteht und der Betroffene hernach gegebenenfalls noch zwei weitere Rechtsmittelinstanzen (kantonales Verwaltungsgericht, Bundesgericht) anrufen kann. Wie sich aus den vom Beschwerdeführer selber eingereichten Akten ergibt (vgl. Beschwerdebeilage 11), hat die zuständige kantonale Polizei- und Militärdirektion nach Kenntnisnahme der neuesten Unterlagen aus dem strafrechtlichen Dossier den bereits geschlossenen Schriftenwechsel und das Beweisverfahren aber kürzlich wieder geöffnet (Verfügung vom 10. April 2008) und den Beteiligten Gelegenheit zur Stellungnahme bis zum 2. Mai 2008 eingeräumt. Es ist nicht ausgeschlossen, dass die instruierende Rechtsmittelbehörde die aufschiebende Wirkung der Beschwerde nach Massgabe von Art. 68 des kantonalen Gesetzes vom 23. Mai 1989 über die Verwaltungsrechtspflege (VRPG) entziehen wird, was umso eher möglich erscheint, als mit der angeordneten Ausweisung nicht etwa in ein gefestigtes Anwesenheitsrecht des Beschwerdeführers - dessen Aufenthaltsbewilligung bereits abgelaufen ist - eingegriffen wird.
Jedenfalls sind die Voraussetzungen für eine sofortige Entlassung des Beschwerdeführers aus der Ausschaffungshaft vorliegend klarerweise nicht gegeben; es wird Sache des Haftgerichts sein, an der ohne Verzug neu anzusetzenden mündlichen Verhandlung - unter korrekter Gewährung des rechtlichen Gehörs - über die Zulässigkeit dieser Administrativmassnahme neu zu befinden.
5. Dies führt zur teilweisen Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheides. Die Sache ist zur unverzüglichen Durchführung einer neuen mündlichen Verhandlung an das Haftgericht zurückzuweisen. Im Übrigen ist die Beschwerde abzuweisen.
Bei diesem Verfahrensausgang sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 3 BGG). Der Kanton Bern hat dem nur teilweise obsiegenden Beschwerdeführer eine reduzierte Parteientschädigung auszurichten (<ref-law>). Dessen Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist insoweit gegenstandslos geworden. Im Übrigen muss dieses Gesuch mangels ernsthafter Erfolgsaussichten des Beschwerdebegehrens Ziff. 2 (Haftentlassung) abgewiesen werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und der Entscheid des Haftgerichts III Bern-Mittelland vom 22. April 2008 aufgehoben.
2. Die Sache wird zur unverzüglichen Durchführung einer neuen mündlichen Verhandlung an das genannte Haftgericht zurückgewiesen.
3. Das Begehren um sofortige Entlassung aus der Haft wird abgewiesen.
4. Es werden keine Kosten erhoben.
5. Der Kanton Bern hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine reduzierte Parteientschädigung von Fr. 1'000.-- auszurichten.
6. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird, soweit es nicht gegenstandslos geworden ist, abgewiesen.
7. Dieses Urteil wird den Parteien, dem Haftgericht III Bern-Mittelland, der Polizei- und Militärdirektion des Kantons Bern und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 30. Mai 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Klopfenstein