Get the Doxie scanner http://getdoxie.com/ ! It is fast and small, and great for scanning a few documents every now and then. It comes with software that is nicely integrated with the most common cloud services etc.
For me, my "paper load" was not big enough to warrant a bigger purchase of a multiple-page scanner, so if you are still in the paper less minor leagues like me, it is a great choice.
As far as I know there's no Linux support for the Doxie, so you're out of luck there. The ScanSnaps, while being quite a bit more expensive and bigger do have a decent support.
If we're only talking about the odd invoice, any normal scanner would do, too. If you get one of those printer/scanner combinations, you'll also save some space.
Yes, the app situation for Linux isn't that good. The Evernote web app alone isn't as comfortable as a native application, and I haven't seen anything decent out of the open source sector.
I'd recommend going a bit more low-tech. Create a script that invokes the "scanimage" command with the desired parameters, then moves it to your "cloud" directory (Dropbox, Ubuntu One etc.). There, run OCR software over it, dumping the result in a file. If nothing major has changed, tesseract would be the free OCR software of choice.
For simplicity's sake, I'd recommend that the script automatically chooses the file name, you just add some "tags", e.g. if your script is called "scan_stuff", you'd invoke it as "scan_stuff amazon invoice", and the result would end up as "~/Dropbox/scans/2011-09-13-14-46-amazon-invoice.pdf", alongside a "2011-09-13-14-46-amazon-invoice.txt" file generated from that. This makes it easy enough to search by date or by a rather generic type.
The SANE scanimage command supports batch mode, even if you don't have an automatic feeder (--batch-prompt).
This might not be as automatic as some of the specialized solutions for Windows or Mac, but it does handle special cases a bit better. You can just have a parameter or separate script for that and don't have to mess with Preferences each time something slightly different comes in (e.g. color, higher dpi, different target directory…).
For me, my "paper load" was not big enough to warrant a bigger purchase of a multiple-page scanner, so if you are still in the paper less minor leagues like me, it is a great choice.