Well, my coin just arrived ... back in Spain.
The geniuses at the USPS were unable to deliver it since the state was missing from the address (but street, town and 5+4 zip code were there). I guess the USPS haven't yet figured out what zip codes mean.
So here's the timeline:
Oct 4th coin is shipped from Spain
Nov 4th I file a missing mail search request with USPS
Nov 8th search request rejected due to "insufficient search request data" (they want to know what the package *looks* like - evidentially tracking number is not enough)
Nov 9th I refile missing mail search request will sellers description of package
Dec 4th USPS acknowledges receipt of my missing mail request. They are now processing it!
Dec 8th Seller sends me photo of package, now back in his hands in Spain
On my USPS "informed delivery" dashboard the package is still showing as status unknown, despite USPS having sent it back to Spain.
So, now the seller is going to reship it.
Now that we're entering Christmas season, I guess I'm in for another 1-2 month wait.