Thanks a lot for raising this question, and @mhoran_psprep thanks a ton for the answer too.
Struggled a bit to figure out the address that need to be used when we go for Non-USPS. In my case FedEx would not accept the below address:
Department of the Treasury,
Internal Revenue Service,
Austin, Texas 73301-0215.
They ask for a physical street address instead. Here is the Austin address I ended up having to use to ship with FedEx:
Internal Revenue Submission Processing Center,
3651 South Interregional Highway 35,
Austin, TX 78741.
I had called the Customer Care and stayed on call for a while to figure it out; I hope my answer might help some one else.
Here's a link to the IRS' own list of addresses for processing centers, containing addresses for centers beyond Austin.