When munging data like this to extract the stuff that you want, just keep breaking your problem up into smaller pieces (as long as you can break the pieces up reliably!). Then when you can't break things up in a perfectly reliable way, you need to alter your data (or your thinking) until you can get it into a format that will allow you to reliably break it up.
For example, you have one big file with data about several hosts. So, use a peachy keen regexp to break the big file into chunks of data pertaining to each host -- (i.e. splitting the data on the dashes / hostnames / dashes parts). Then, each host's chunk of data has information about software packages. So, split that chunk into its pieces -- (i.e. splitting on the 2 blank lines to get each piece of software). Finally, you reach some slightly inconsistent data. Sometimes you have the software name, a blank line, then patch level information. But for one, there is no blank line separator. SO, rather than splitting on the blank line, you should just pull the first non-blank line from each record to get the software package name. All that's left is your patch info.
If you break it down like this, data munging becomes easy! As long as you know enough about regular expressions, which you can find from many of the good Perl books or the links
stephen mentions.
Or you can just use
tachyon's code above -- and hope that every time you need something like this, someone will be just as helpful. :)