Steven Zahm@ Paul
Right, searches of strings 3 character or less will not return a result. However, when submitting nothing thru search, no search is being performed, at all. The default output is to list the entire directory unless the template supports pagination in which case the output would be paginated. If you were to visit the page with the [connections] shortcode, you would see the same end result as the user who did an empty search. Since you have 4500+ entries, you should really have a template that support paginated results. Depending on your exact usage requirements, you could perhaps use the undocumented limit shortcode option like so: [connections limit=100]. Since you’re only searching for names, that very well could be a viable option.
Hope that helps.