I would send in the requested info (even if it is a hassle) if for no other reason than to find out what caused the inquiry. If you were a 'new' card holder I could understand, but you've been with Capital One for a bit now, and it seems like something specific has them concerned.
Also, I 'feel your pain' regarding having no utilities in your name; I would have the same problem. I have paperwork from BCBS with my name (and address) that I have depended on in the past for similar purposes.
