I think the simple answer is to reboot. It sounds like you manually deleted it from the Applications directory and the other locations you checked instead of using the uninstaller. I did the same thing in the past. To run the uninstaller, you would have to install it again. However, if you just reboot it is almost certainly not going to start the toolbar thing again because you already checked a bunch of startup locations.

Then there would be no need to purge the remaining files but if you really wanted to you could just search for them and rm.

sudo find / -name "*malwarebytes*"

/usr/local/Homebrew/Library/Taps/caskroom/homebrew-cask/Casks/malwarebytes.rb /Library/Application Support/Malwarebytes/MBAM/Settings/1/com.malwarebytes.mbam.telemetry /Library/Application Support/Malwarebytes/MBAM/Settings/1/com.malwarebytes.mbam.rtprotection /Library/Application Support/Malwarebytes/MBAM/Settings/501/com.malwarebytes.mbam.frontend /Library/Application Support/Malwarebytes/MBAM/Settings/com.malwarebytes.mbam.settings /Library/Application Support/Malwarebytes/MBAM/Settings/201/com.malwarebytes.mbam.frontend /Library/Extensions/com.malwarebytes.mbam.rtprotection.kext /Library/Extensions/com.malwarebytes.mbam.rtprotection.kext/Contents/MacOS/com.malwarebytes.mbam.rtprotection /private/var/db/receipts/com.malwarebytes.mbam.bom /private/var/db/receipts/com.malwarebytes.mbam.plist /private/var/db/BootCaches/450CDCCC-22F9-44F3-AD49-712500F960C9/app.com.malwarebytes.mbam.frontend.application.playlist /private/var/db/nsurlsessiond/Library/Caches/com.apple.nsurlsessiond/Downloads/com.malwarebytes.mbam.rtprotection.daemon /private/var/folders/8m/6dsl12z52g7b_9f4kh1yb0s40000gn/C/com.malwarebytes.mbam.frontend.application /private/var/folders/8m/6dsl12z52g7b_9f4kh1yb0s40000gn/C/com.malwarebytes.mbam.frontend.agent

I think the simple answer is to reboot. It sounds like you manually deleted it from the Applications directory and the other locations you checked instead of using the uninstaller. I did the same thing in the past. To run the uninstaller, you would have to install it again. However, if you just reboot it is almost certainly not going to start the toolbar thing again because you already checked a bunch of startup locations.

Then there would be no need to purge the remaining files but if you really wanted to you could just search for them

$ sudo find / -name '*malwarebytes*'
/usr/local/Homebrew/Library/Taps/.../malwarebytes.rb
/Library/Application Support/Malwarebytes/.../com.malwarebytes.mbam.telemetry 
...
/private/var/folders/8m/.../C/com.malwarebytes.mbam.frontend.agent

and/or directly delete them

$ sudo find / -name '*malwarebytes*' -delete