Is it possible to spend outputs with very small amounts? I'm a Bitcoin newbie and this is rather theoretical question based on this discussion's accepted answer: transaction creation failed  

So does it essentially mean that in case if my wallet is comprised of many small amounts of BTC (say, each of them is less than current tx fee), even though they may sum up to substantial amount, I nevertheless won't be able to spend any of them?

For example, let's say in the edge case I have 100.000.000 addresses each containing 1 Satoshi. Does it mean 1 BTC they all sum up to is lost irrevocably?
They won't be lost. But it won't be easy to get them recovered.
The wiki page on Transaction Fees mentions the following:

A transaction may be safely sent without fees if these conditions are met:

It is smaller than 10,000 bytes.
All outputs are 0.01 BTC or larger.
Its priority is large enough (see the Technical Info section below)


So if you have 1,000,000 outputs with one satoshi, you can bundle them by combining them few at a time with a larger output.
Let's say you have another output of 1 BTC. You can make a transaction using this output and any number of 1-satoshi outputs until the limit of 10kB is reached. Make the transaction create only one new output.
I'm not very familiar with output sizes, but let's plan for the worse and consider you can only add two inputs (this will probably not be the case). You will need to make 1,000,000 free transactions each combining the 1-satoshi with the 1 BTC. First tx will give you an 1,000,001 Satoshi output for that address and so on.
So basically, 1-satoshi outputs are not lose, but they are hard to spend. However, the price will need to increase substantially until it's worth the effort to go through this hassle in order to free some satoshi.