I, too, am running 8.04 and my Nautilus is 2.22.5.1

You're correct about "View -> Visible Columns".

The only way I can see to get the full path is to right click on
each found file and select "Properties"; the "Location:" has the
full path which can be copy'n'pasted as required, but then you
need to still copy'n'paste the filename, too. Painful.

The File -> Save Search As ... only saves the search query, not
the results.

I don't see anything else or another way to get the search results
into a file.