The folowing solution was tested with bbdb version 2.35: http://bbdb.sourceforge.net/
I gave the bounty-bonus to @Jules Tamagnan for his interesting approach to displaying the entire record as a potential completion candidate.
The following answer provides for tab-completion using the name field of the database --
completing-read does not require a match because that optional argument has been omitted.
(defun bbdb-search-with-completion (elidep)
"Display all entries in the BBDB matching the regexp STRING
in either the name(s), company, network address, or notes.
Press the tab key for possible name completions without requiring a match."
(string (completing-read "bbdb (regexp): " ht 'bbdb-completion-predicate))
(bbdb-display-layout (bbdb-grovel-elide-arg elidep))
(notes (cons '* string))
(records (bbdb-search (bbdb-records) string string string notes nil)))
(message "No records matching '%s'" string))))