FirebaseでPUSH通知（FCM）のユーザーセグメントに関して、正しく理解されていない情報がいくつかあり、googleの公式ドキュメント上でも明確な記載がなく、混乱したので書いておきます。（2018年末現在）
※あと、Googleの公式ドキュメントはEnglishでみないと更新されてないことが多々あるよね（汗
伝えたいこと
ユーザーセグメントするためには、主にユーザー（Audiences）とユーザープロパティ（User Property）の２つの方法がありますが、最近仕様が変わったり、混同していたりするので、正しく理解しましょう。
ユーザー（Audiences）
Audiencesにてユーザーに対し複数条件をフィルターすることができます。イベントやユーザープロパティを組み合わせ作成できます。
※ただし注意が必要です！
これまでAudiencesに追加されると、そのユーザーは永遠にその属性を持ち続ける仕様でしたが、2018/10/29から仕様が変わり「有効期限（Membership duration）」が追加されました。そのため、Audiencesに属したユーザーは任意の有効期限までその属性を持つことになります。
2018/10/29リリースノートに記載があります。
October 29, 2018
Added support for dynamic audiences that determine membership based on the current value of user properties. You can also now specify criteria for when your users leave an audience such as membership duration, exclusion criteria, or specific time periods. For more information, see Audiences.
https://firebase.google.com/support/releases?hl=en
またAudiencesについて、iOS-SDKのバージョンも注意が必要そうです。
Version 5.2.0 of the Firebase Analytics framework is required to use the full set of audience capabilities on iOS.
https://support.google.com/firebase/answer/6317509?hl=en
※Android-SDKへの明記はありませんでした。
ユーザープロパティ（User Property）
ユーザープロパティをセグメントに利用する場合は、最新のプロパティでセグメントしてくれます。
※ただし注意が必要です！
ユーザープロパティがセグメントに適用されるまでにFirebase側の同期タイミングでの遅延が起きるようです。
手元の実験ではユーザープロパティがiOSアプリ上で変更された1時間ほどあとにFCMを発射させても、変更が反映されず通知が届いてほしくないユーザーに通知が届いてしまいました。（Audiencesのように永続するのかと勘違いしそうでした）
半日ほど置いた後に発射させたときには、通知が届かなくなりました。反映に遅延があることを理解しましょう。
最後に
Firebase周りはまだまだ進化途中なので、古いqiita情報などを鵜呑みにせず、公式ドキュメント（英語）を読みましょう。そしてわからないことがあったら、誰かに聞こう。（今回の件も、とある有識者に協力頂きました。ありがとうございました。）