Hi @JKFrancis
Create the entry in User Configuration > Policies > Preferences > Windows Settings > Registry on your GPO and it should work. Just tested this as I was also having the same issue.
Action : Update
Hive : HKEY_CURRENT_USER
Key Path : Software\Microsoft\Windows\CurrentVersion\Search
Value Name : SearchboxTaskbarMode
Value Type : REG_DWORD
Value Data: 00000000
Base : Hexadecimal