So I checked it out with the U.S. Post Office (1-800-238-5355) and they confirmed that it is indeed legal!!
1	So	so	ADV	RB	_	3	advmod	3:advmod	_
2	I	I	PRON	PRP	Case=Nom|Number=Sing|Person=1|PronType=Prs	3	nsubj	3:nsubj	_
3	checked	check	VERB	VBD	Mood=Ind|Number=Sing|Person=1|Tense=Past|VerbForm=Fin	0	root	0:root	_
4	it	it	PRON	PRP	Case=Acc|Gender=Neut|Number=Sing|Person=3|PronType=Prs	3	obj	3:obj	_
5	out	out	ADP	RP	_	3	compound:prt	3:compound:prt	_
6	with	with	ADP	IN	_	10	case	10:case	_
7	the	the	DET	DT	Definite=Def|PronType=Art	10	det	10:det	_
8	U.S.	U.S.	PROPN	NNP	Number=Sing	10	compound	10:compound	_
9	Post	Post	PROPN	NNP	Number=Sing	10	compound	10:compound	_
10	Office	Office	PROPN	NNP	Number=Sing	3	obl	3:obl:with	_
11	(	(	PUNCT	-LRB-	_	12	punct	12:punct	SpaceAfter=No
12	1-800-238-5355	1-800-238-5355	NUM	CD	NumForm=Digit|NumType=Card	10	list	10:list	SpaceAfter=No
13	)	)	PUNCT	-RRB-	_	12	punct	12:punct	_
14	and	and	CCONJ	CC	_	16	cc	16:cc	_
15	they	they	PRON	PRP	Case=Nom|Number=Plur|Person=3|PronType=Prs	16	nsubj	16:nsubj	_
16	confirmed	confirm	VERB	VBD	Mood=Ind|Number=Plur|Person=3|Tense=Past|VerbForm=Fin	3	conj	3:conj:and	_
17	that	that	SCONJ	IN	_	21	mark	21:mark	_
18	it	it	PRON	PRP	Case=Nom|Gender=Neut|Number=Sing|Person=3|PronType=Prs	21	nsubj	21:nsubj	_
19	is	be	AUX	VBZ	Mood=Ind|Number=Sing|Person=3|Tense=Pres|VerbForm=Fin	21	cop	21:cop	_
20	indeed	indeed	ADV	RB	_	21	advmod	21:advmod	_
21	legal	legal	ADJ	JJ	Degree=Pos	16	ccomp	16:ccomp	SpaceAfter=No
22	!!	!!	PUNCT	.	_	3	punct	3:punct	_
