I'm having difficulty removing the begin2search program/toolbar.

Here's what I've done so far:
I ran both adaware and spybot and removed all spyware and references to begin2search and then I used hijack this to remove the suspicious looking entries. I then restarted my computer only to find that begin2search is still lurking somewhere because the words 'google', 'music' etc are still linked to begin2search sites. The search function is no longer redirected to begin2search though (as spybot blocked begin2search from changing it)

Here's my hijack this log:

Logfile of HijackThis v1.97.7
Scan saved at 3:58:30 PM, on 24/11/2004
Platform: Windows XP SP2 (WinNT 5.01.2600)
MSIE: Internet Explorer v6.00 SP2 (6.00.2900.2180)

Running processes:
C:\WINDOWS\System32\smss.exe
C:\WINDOWS\system32\winlogon.exe
C:\WINDOWS\system32\services.exe
C:\WINDOWS\system32\lsass.exe
C:\WINDOWS\system32\svchost.exe
C:\WINDOWS\System32\svchost.exe
C:\WINDOWS\system32\spoolsv.exe
C:\Program Files\Common Files\Symantec Shared\ccProxy.exe
C:\Program Files\Common Files\Symantec Shared\ccSetMgr.exe
C:\Program Files\Norton Internet Security\Norton AntiVirus\navapsvc.exe
C:\WINDOWS\System32\nvsvc32.exe
C:\Program Files\Common Files\Symantec Shared\SNDSrvc.exe
C:\WINDOWS\System32\svchost.exe
C:\WINDOWS\Explorer.EXE
C:\Program Files\Common Files\Symantec Shared\CCPD-LC\symlcsvc.exe
C:\Program Files\Common Files\Symantec Shared\ccEvtMgr.exe
C:\Program Files\Common Files\Symantec Shared\Security Center\SymWSC.exe
C:\WINDOWS\system32\ps2.exe
C:\Program Files\Telstra\Cable Login\bpcable.exe
C:\WINDOWS\system32\RUNDLL32.EXE
C:\Program Files\Common Files\Symantec Shared\ccApp.exe
C:\Program Files\Telstra\Toolbar\bpumTray.exe
C:\Program Files\ScanSoft\OmniPageSE\opware32.exe
C:\Program Files\IMT Labs Messenger Plugin\Cloud.exe
C:\Program Files\Common Files\Real\Update_OB\realsched.exe
C:\Program Files\Messenger\msmsgs.exe
C:\Program Files\MSN Messenger\msnmsgr.exe
C:\Program Files\Spybot - Search & Destroy\TeaTimer.exe
C:\Program Files\Norton Internet Security\Norton AntiVirus\SAVScan.exe
C:\Program Files\Internet Explorer\iexplore.exe
C:\Documents and Settings\Owner\Local Settings\Temporary Internet Files\Content.IE5\CHY3WPU7\HijackThis[1].exe

O2 - BHO: (no name) - {06849E9F-C8D7-4D59-B87D-784B7D6BE0B3} - C:\Program Files\Adobe\Acrobat 6.0\Reader\ActiveX\AcroIEHelper.dll
O2 - BHO: (no name) - {243B17DE-77C7-46BF-B94B-0B5F309A0E64} - c:\Program Files\Microsoft Money\System\mnyside.dll
O2 - BHO: (no name) - {4C7B6DE1-99A4-4CF1-8B44-68889900E1D0} - C:\Program Files\Telstra\Toolbar\bpumToolBand.dll
O2 - BHO: (no name) - {53707962-6F74-2D53-2644-206D7942484F} - C:\PROGRA~1\SPYBOT~1\SDHelper.dll
O2 - BHO: Web assistant - {9ECB9560-04F9-4bbc-943D-298DDF1699E1} - C:\Program Files\Common Files\Symantec Shared\AdBlocking\NISShExt.dll
O2 - BHO: NAV Helper - {BDF3E430-B101-42AD-A544-FADC6B084872} - C:\Program Files\Norton Internet Security\Norton AntiVirus\NavShExt.dll
O2 - BHO: ohb - {CB5B2BC6-F957-4D8A-BE67-83F3EC58BA01} - C:\WINDOWS\system32\dsktrf.dll
O2 - BHO: (no name) - {FDD3B846-8D59-4ffb-8758-209B6AD74ACC} - (no file)
O3 - Toolbar: Web assistant - {0B53EAC3-8D69-4b9e-9B19-A37C9A5676A7} - C:\Program Files\Common Files\Symantec Shared\AdBlocking\NISShExt.dll
O3 - Toolbar: Norton AntiVirus - {42CDD1BF-3FFB-4238-8AD1-7859DF00B1D6} - C:\Program Files\Norton Internet Security\Norton AntiVirus\NavShExt.dll
O3 - Toolbar: Easy-WebPrint - {327C2873-E90D-4c37-AA9D-10AC9BABA46C} - C:\Program Files\Canon\Easy-WebPrint\Toolband.dll
O3 - Toolbar: BigPond Toolbar - {7A431EC4-CC21-4DF7-9DB1-A2CF74C4CC98} - C:\Program Files\Telstra\Toolbar\bpumToolBand.dll
O4 - HKLM\..\Run: [IMJPMIG8.1] "C:\WINDOWS\IME\imjp8_1\IMJPMIG.EXE" /Spoil /RemAdvDef /Migration32
O4 - HKLM\..\Run: [MSPY2002] C:\WINDOWS\System32\IME\PINTLGNT\ImScInst.exe /SYNC
O4 - HKLM\..\Run: [PHIME2002ASync] C:\WINDOWS\System32\IME\TINTLGNT\TINTSETP.EXE /SYNC
O4 - HKLM\..\Run: [PHIME2002A] C:\WINDOWS\System32\IME\TINTLGNT\TINTSETP.EXE /IMEName
O4 - HKLM\..\Run: [Recguard] C:\WINDOWS\SMINST\RECGUARD.EXE
O4 - HKLM\..\Run: [NvCplDaemon] RUNDLL32.EXE C:\WINDOWS\System32\NvCpl.dll,NvStartup
O4 - HKLM\..\Run: [PS2] C:\WINDOWS\system32\ps2.exe
O4 - HKLM\..\Run: [BigPondCable] "C:\Program Files\Telstra\Cable Login\bpcable.exe" /r
O4 - HKLM\..\Run: [NvMediaCenter] RUNDLL32.EXE C:\WINDOWS\System32\NvMcTray.dll,NvTaskbarInit
O4 - HKLM\..\Run: [ccApp] "C:\Program Files\Common Files\Symantec Shared\ccApp.exe"
O4 - HKLM\..\Run: [URLLSTCK.exe] C:\Program Files\Norton Internet Security\UrlLstCk.exe
O4 - HKLM\..\Run: [BigPond Toolbar] "C:\Program Files\Telstra\Toolbar\bpumTray.exe"
O4 - HKLM\..\Run: [Omnipage] C:\Program Files\ScanSoft\OmniPageSE\opware32.exe
O4 - HKLM\..\Run: [Symantec NetDriver Monitor] C:\PROGRA~1\SYMNET~1\SNDMon.exe
O4 - HKLM\..\Run: [CloudPlugin] "C:\Program Files\IMT Labs Messenger Plugin\Cloud.exe"
O4 - HKLM\..\Run: [TkBellExe] "C:\Program Files\Common Files\Real\Update_OB\realsched.exe" -osboot
O4 - HKCU\..\Run: [Symantec NetDriver Monitor] C:\PROGRA~1\SYMNET~1\SNDMon.exe
O4 - HKCU\..\Run: [MSMSGS] "C:\Program Files\Messenger\msmsgs.exe" /background
O4 - HKCU\..\Run: [msnmsgr] "C:\Program Files\MSN Messenger\msnmsgr.exe" /background
O4 - HKCU\..\Run: [SpybotSD TeaTimer] C:\Program Files\Spybot - Search & Destroy\TeaTimer.exe
O8 - Extra context menu item: Easy-WebPrint Add To Print List - res://C:\Program Files\Canon\Easy-WebPrint\Resource.dll/RC_AddToList.html
O8 - Extra context menu item: Easy-WebPrint High Speed Print - res://C:\Program Files\Canon\Easy-WebPrint\Resource.dll/RC_HSPrint.html
O8 - Extra context menu item: Easy-WebPrint Preview - res://C:\Program Files\Canon\Easy-WebPrint\Resource.dll/RC_Preview.html
O8 - Extra context menu item: Easy-WebPrint Print - res://C:\Program Files\Canon\Easy-WebPrint\Resource.dll/RC_Print.html
O9 - Extra 'Tools' menuitem: Sun Java Console (HKLM)
O9 - Extra button: MoneySide (HKLM)
O9 - Extra button: Messenger (HKLM)
O9 - Extra 'Tools' menuitem: Windows Messenger (HKLM)
O15 - Trusted Zone: http://www.vcaa.vic.edu.au
O16 - DPF: {22222222-2222-2222-2222-222222222222} - file://c:\x.cab
O16 - DPF: {2917297F-F02B-4B9D-81DF-494B6333150B} (Minesweeper Flags Class) - http://messenger.zone.msn.com/binary/MineSweeper.cab31267.cab
O16 - DPF: {4C39376E-FA9D-4349-BACC-D305C1750EF3} (EPUImageControl Class) - http://tools.ebayimg.com/eps/wl/activex/EPUWALControl_v1-0-3-12.cab
O16 - DPF: {4D7F48C0-CB49-4EA6-97D4-04F4EACC2F3B} (InstallShield Setup Player 2K2) - http://sib1.od2.com/common/Member/ClientInstall/10.00.0036/OCI/setup.exe
O16 - DPF: {6414512B-B978-451D-A0D8-FCFDF33E833C} (WUWebControl Class) - http://v5.windowsupdate.microsoft.com/v5consumer/V5Controls/en/x86/client/wuweb_site.cab?1096093447437
O16 - DPF: {77E32299-629F-43C6-AB77-6A1E6D7663F6} (Groove Control) - http://www.nick.com/common/groove/gx/GrooveAX27.cab
O16 - DPF: {8E0D4DE5-3180-4024-A327-4DFAD1796A8D} (MessengerStatsClient Class) - http://messenger.zone.msn.com/binary/MessengerStatsClient.cab30149.cab
O16 - DPF: {A8658086-E6AC-4957-BC8E-8D54A7E8A790} (GDIChk Object) - http://www.microsoft.com/security/controls/GDI/0/GDIChk.CAB
O16 - DPF: {D27CDB6E-AE6D-11CF-96B8-444553540000} (Shockwave Flash Object) - http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab
O16 - DPF: {E2F9D054-D2B5-4CE8-9BDF-8BF3A81DB7E9} (ProductIDGatherer.WindowsGatherer) - http://download.microsoft.com/download/a/3/7/a377aea1-7b14-4fa1-933c-43e657b37995/ProductIDGatherer.CAB
O16 - DPF: {F58E1CEF-A068-4C15-BA5E-587CAF3EE8C6} (MSN Chat Control 4.5) - http://chat.msn.com/bin/msnchat45.cab
O16 - DPF: {F6BF0D00-0B2A-4A75-BF7B-F385591623AF} (Solitaire Showdown Class) - http://messenger.zone.msn.com/binary/SolitaireShowdown.cab30149.cab

Any help would be greatly appreciated. Thanks in advance.

Dunno if you've already solved this, but you might want to check your Hosts file:
C:\WINDOWS\system32\drivers\etc\Hosts

There should only be the default entry in there:
127.0.0.1 localhost

When windows does a DNS lookup, it first consults this file to see if the host name/IP address mapping is in there. Some malware will create entries in there, pointing things like google and yahoo at their own servers. If you see other entries in there, especially ones that say google, you should delete them.

Go to this post here first, and follow the instructions EXACTLY.
How to remove Begin2Search / Coolwebsearch
Then see How to post your Hijackthis log-files.