So Thank you guys for your help. At the end I went with the solution suggested by westconn1. He's helped me in other ocassions and he has been fundamental to what I am doing right now.

I wanted to share how it all turned out, It's now working perfectly after several tests, now I just need to add the error handling to it and it would be finished, at least this part. So here is how it went:


Code:
If ANDTxtBox.Text = "" And ORTxtBox.Text = "" And NOTTxtBox.Text = "" Then

    MsgBox " Please enter at least 1 search term", vbCritical, "Input Needed"
Else
StrValue = Sheets("Panel").Range("C2").Value
StrSwitch = Sheets("Panel").Range("D2").Value

'AND
If ORTxtBox.Text = "" Then

mystr = ANDTxtBox.Text
myarr = Split(mystr, ",")
For i = 0 To UBound(myarr)
    If InStr(Trim(myarr(i)), " ") > 0 Then
        myarr(i) = """" & Trim(myarr(i)) & """"
        Else: myarr(i) = Trim(myarr(i))
    End If
Next
mystr = Join(myarr, " AND ")

ANDTxtBox = mystr

'ENCODED
ANDOp = Replace(Replace(Replace(ANDTxtBox.Text, StrValue, StrSwitch), "#", "%" & Hex(Asc("#"))), "+", "%" & Hex(Asc("+")))

'NOT ENCODED
ANDNotEncoded = Replace(ANDTxtBox.Text, StrValue, StrSwitch)


Else
If ANDTxtBox.Text <> "" And ORTxtBox.Text <> "" Then

mystr = ANDTxtBox.Text
myarr = Split(mystr, ",")
For i = 0 To UBound(myarr)
    If InStr(Trim(myarr(i)), " ") > 0 Then
        myarr(i) = """" & Trim(myarr(i)) & """"
        Else: myarr(i) = Trim(myarr(i))
    End If
Next
mystr = Join(myarr, " AND ")

ANDTxtBox = mystr
' ENCODED
StrReplace = Replace(Replace(Replace(ANDTxtBox.Text, StrValue, StrSwitch), "#", "%" & Hex(Asc("#"))), "+", "%" & Hex(Asc("+")))
ANDOp = StrReplace & " AND ("

' NOT ENCODED
StrReplaceNotEncoded = Replace(ANDTxtBox.Text, StrValue, StrSwitch)
ANDNotEncoded = StrReplaceNotEncoded & " AND ("


End If
End If

'OR
If ANDTxtBox.Text = "" Then
mystr = ORTxtBox.Text
myarr = Split(mystr, ",")
For i = 0 To UBound(myarr)
    If InStr(Trim(myarr(i)), " ") > 0 Then
        myarr(i) = """" & Trim(myarr(i)) & """"
        Else: myarr(i) = Trim(myarr(i))
    End If
Next
mystr = Join(myarr, " OR ")

ORTxtBox = mystr

'ENCODED
ORop = Replace(Replace(Replace(ORTxtBox.Text, StrValue, StrSwitch), "#", "%" & Hex(Asc("#"))), "+", "%" & Hex(Asc("+")))

'NOT ENCODED
ORopNotEncoded = Replace(ORTxtBox.Text, StrValue, StrSwitch)

Else

If ANDTxtBox.Text <> "" And ORTxtBox.Text <> "" Then
mystr = ORTxtBox.Text
myarr = Split(mystr, ",")
For i = 0 To UBound(myarr)
    If InStr(Trim(myarr(i)), " ") > 0 Then
        myarr(i) = """" & Trim(myarr(i)) & """"
        Else: myarr(i) = Trim(myarr(i))
    End If
Next
mystr = Join(myarr, " OR ")
ORTxtBox = mystr

'ENCODED
StrReplace = Replace(Replace(Replace(ORTxtBox.Text, StrValue, StrSwitch), "#", "%" & Hex(Asc("#"))), "+", "%" & Hex(Asc("+")))
ORop = StrReplace & ")"

'NOT ENCODED
StrReplaceNotEncoded = Replace(ORTxtBox.Text, StrValue, StrSwitch)
ORopNotEncoded = StrReplaceNotEncoded & ")"

End If
End If

'NOT
If NOTTxtBox.Text <> "" Then
mystr = NOTTxtBox.Text
myarr = Split(mystr, ",")
For i = 0 To UBound(myarr)
    If InStr(Trim(myarr(i)), " ") > 0 Then
        myarr(i) = """" & Trim(myarr(i)) & """"
        Else: myarr(i) = Trim(myarr(i))
    End If
Next
mystr = Join(myarr, " -")

NOTTxtBox = "-" & mystr

'ENCODED
NOTop = Replace(Replace(Replace(NOTTxtBox.Text, StrValue, StrSwitch), "#", "%" & Hex(Asc("#"))), "+", "%" & Hex(Asc("+")))

'NOT ENCODED
NOTopNotEncoded = Replace(NOTTxtBox.Text, StrValue, StrSwitch)

End If
End If

SearchInput = location & identifier & ANDOp & ORop & NOTop
TextBox3.Text = location & identifier & ANDNotEncoded & ORopNotEncoded & NOTopNotEncoded

I had to separate the "Encoded" string from the Non Encoded one since it would look funny as a text and the user may be like: so wht the hell are those symbols? so I separated them into an Encoded and Not Encoded one.


Thank you guys again!


Techgnome: Your information on URL Encoding was so enlighting! I have now a list of other chars that may cause trouble and I know how to call that Encoding Function if I need it later, I have pasted it into a separate module just to have it close to me. THanks for that too.