How do you store and catalog your vinyl?

My collection was about the size of yours when I started to organize it last year with Discogs. I got a couple of Kallax shelving units from IKEA and went to town. While organizing, I noticed two things: several records I thought I had I did not (lost in multiple moves, stolen, gotten rid of...) and I had a few records I had no idea how I got them. I quickly started culling and adding, all the while finally LISTENING to my records. Just hit 1500 this week, so beware. 

I organize first by a few categories ..... symphonies, chamber music, other orchestra, and then by composer within each group.  Then jazz, singer-songwriters, early rock, test/demo records, and misc other.  Within these I arrange alphabetically by performer.  I've got over 1200 lps, and 1100 cds, and the system works for me.

I do this because I usually choose what to listen to by category first, e.g. I fell like listening to Judy Collins tonight ... then it is easy to remember to go to singer-songwriters and find "Collins" group of discs.  Then make a choice.

A lot of great suggestions. 

On organization - here are 10 different methods to organize. I bet there is at least one way you've never thought of, and might like. I'm actually a fan of release year.

http://www.vinylmeplease.com/magazine/organizing-your-record-collection/

You sound like you are slow to jump into an app to organize. You have nothing in the world to lose trying out Discogs. Put in a couple of albums and see if you like it. There is a massive benefit to that system - the notes people have submitted are incredible. Honestly, given the love for details, I'm surprised more people didn't say Discogs as no other way to do this. 

In those Discogs listings are more details about each release than you can ever imagine. My personal favorite - runout / matrix listings. You can pretty much definitively determine which release you own. Honestly, dollar value is fun, but a lot less useful. 

And, if you are ever out buying records, you will never buy a duplicate.

uberwaltz - That's me. I have 7,000 CDs (5,500) stored in metal cabinets with custom drawers http://www.can-am.ca/  and 1,000 on shallow bookcase shelving.  The box sets are separated on top of the shelving.  These are cataloged.

The 7,000 78s and 15,000 LPs that are also cataloged are stored in built-in wall shelving units (withstood 6.9 1994 Northridge earthquake with a touch/ 1/16th inch movement at most) anchored to my 8"-12" thick double studded, double drywalled walls and 6" concrete slab with 3/4" rebar reinforcement).  

The other 10,000 LPs are mostly stored in racks bought at Costco.

As to cataloging, I use MS Word with separate categories for each genre, just like the shelved LPs/78s/CDs are placed. 
Cataloging & Shelving Categories:
1 A Orchestral by composer,
1 B Orchestral compilations by conductor,
1 C Soloist Instrumentalists,
1 D Chamber works by group name,
2 Opera Singers recitals,
3 Opera,  
4 Jazz Instrumentalists,
5 Pop/Jazz Vocalists and 1950's R&R,
6 Rock & Roll 1960's to 1980's., 
7 A Musicals by title,
7 B Film by title,
7 C Film compilations by composer,
8 A Yiddish vocalists,
8 B Hebrew vocalists,
8 C Klezmer and other Jewish instrumentalists
8 D Cantorial and
9 Comedy (I have about 800 LPs/CDs of these). 
10 SuperAnalog Japanese/other & Direct Discs There is also a miscellaneous category for storage/cataloging for super analog LPs by label such as Japanese Toshiba/EMI/Sony/etc. and direct to disc.

I put a CD symbol for CDs which are cataloged together with LP, knowing if I have one or both media of the recording.  78s are cataloged similarly but separate from the CD/LPs.  

I have slowed down my cataloging (and buying LPs, basically only CDs and CD sets now) as time does not permit it; however, I haven't cut down on my listening time.

My acquaintances who have/had 1 million or more LPs do/did not have not categorized at all or very well.  What a mish mosh as they generally didn't listen but only collect records. 

My friend with 250,000 78s used index cards and had easy shelving alphabetically by opera, vocalist, instrumentalist and conductor and LPs, all classical or jazz, similarly.