1. Your social is new, and it wont come up on any database yet.
2. Yes lots of members here have had issues with background checks, so comply with what they're asking
3. Future reference, get a letter from the SSA, but even then you're still going to have issues with background checks for the first few years.