Can you search Outlook messages like a database (sort of query for a list of items contained in messages: body, subject, or attachment name)

Yes, that can be done
http://msdn.microsoft.com/en-us/library/office/ff866933(v=office.15).aspx
I suspect though, that you'd need to create a UserForm as a place to enter the strings you'd like and perhaps the results as well.  There could be a fair bit of heavy lifting to that.

How are your Outlook VBA skills?

My Outlook VBA skills are only as good as the skills that will transfer from Excel VBA skills.  Sounding like not good enough though.

What i see from the msdn article doesn't appear to give me the ability to look for a list of things (such as 50-100 different job numbers) and return the results of each of those in a table format (I was likely unclear about wanting a table of results).

All things are possible because Application.AdvancedSearch exists.
Since you know Excel VBA, that's maybe where you should do this from.
I'm an Access guy, primarily, but the guts of it are the same.
This code goes in a module and is used to start Outlook

Option Explicit
Public wasOpen As Boolean
Function StartApp(ByVal appName) As Object
On Error GoTo ErrorHandler
Dim oApp As Object

wasOpen = True
Set oApp = GetObject(, appName)    'Error here - Run-time error '429':
Set StartApp = oApp

Exit Function

ErrorHandler:
If Err.Number = 429 Then
    'App is not running; open app with CreateObject
    Set oApp = CreateObject(appName)
    wasOpen = False
    Resume Next
Else
    MsgBox Err.Number & " " & Err.Description
End If
End Function

Select allOpen in new window

This code, probably in Excel fired from a macro, gets you an Outlook.Application object to work with

Dim objOutlook As Outlook.Application
Dim objOutlookMsg As Outlook.MailItem
Dim objOutlookRecip As Outlook.Recipient
Dim objOutlookAttach As Outlook.Attachment
Dim objOutlookExplorers As Outlook.Explorers


Set objOutlook = StartApp("Outlook.Application")

Dim ns As Outlook.Namespace
Dim Folder As Outlook.MAPIFolder
Set ns = objOutlook.GetNamespace("MAPI")
Set Folder = ns.GetDefaultFolder(olFolderInbox)
Set objOutlookExplorers = objOutlook.Explorers

If wasOpen = False Then
    objOutlookExplorers.Add Folder
    Folder.Display
    'done opening
End If

Select allOpen in new window

Now, from there, from the second example in the linked MSDN article you be looking to set the parameters of
expression .AdvancedSearch(Scope, Filter, SearchSubFolders, Tag) with Excel cell values
Set up this way, where expression would be Application if you were doing it in Outlook, it will be objOutlook

And, at the end of the second example
   Do Until MyTable.EndOfTable  
        Set nextRow = MyTable.GetNextRow()  
       Debug.Print nextRow("Subject")  
    Loop  
Instead of Debug.Print, you'll be looking to write results to Excel cells

Let me know what you think

Nick,
At first glance, I think you're right in the range of what I need.  It'll be a week or two before I really get to sit down and try it out.  Since it is miles ahead of where i started, I'm going to mark this as the answer and close the question.

Thank you for leading me down the path to a solution!

I think you should be able to leave it open.  Don't mark it as answered until it really does have finality for you.
On my part, there's no hurry.

Nick67

After some looking, this will get me there with a bit more time spent.  Thanks for your help!!

Then there's the round-trip, so to speak.
With the details knock into the spreadsheet, you should be able to craft code in Excel that will have Outlook find and select the message of the active cell if that's what you're also after.

AdvancedSearch also permits multiple search criteria.  I only set up for a single row in Excel, but that is certainly extensible.
You may find this of interest, as well
http://www.gregthatcher.com/Scripts/VBA/Outlook/GetListOfOutlookEmails.aspx

Glad to be of service!
Nick67