This shouldn't happen with a straight apt-get remove --purge mysql-client mysql-server, however presumably you also issued some command to reinstall those packages.

Regardless, it sounds like everything should be working now (assuming you have a mailadmin user with appropriate grants for mysql).

That's what I thought too but here's my output(there is a prompt to enter my password thrown in there):

mail ~: sudo apt-get remove --purge  mysql-server mysql-client
[sudo] password for jeff: 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Package mysql-server is not installed, so not removed
The following packages were automatically installed and are no longer required:
  libnet-daemon-perl libhtml-template-perl libdbi-perl libdbd-mysql-perl
  mysql-server-5.0 libterm-readkey-perl mysql-client-5.0 libplrpc-perl
Use 'apt-get autoremove' to remove them.
The following packages will be REMOVED:
  mysql-client*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 81.9kB disk space will be freed.
Do you want to continue [Y/n]? y
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
   LANGUAGE = (unset),
   LC_ALL = (unset),
   LANG = "en_CA.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
(Reading database ... 24442 files and directories currently installed.)
Removing mysql-client ...
Setting up mysql-server-5.0 (5.0.51a-24) ...
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
   LANGUAGE = (unset),
   LC_ALL = (unset),
   LANG = "en_CA.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
/usr/bin/locale: Cannot set LC_CTYPE to default locale: No such file or directory
/usr/bin/locale: Cannot set LC_MESSAGES to default locale: No such file or directory
/usr/bin/locale: Cannot set LC_ALL to default locale: No such file or directory
Stopping MySQL database server: mysqld.
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
   LANGUAGE = (unset),
   LC_ALL = (unset),
   LANG = "en_CA.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
   LANGUAGE = (unset),
   LC_ALL = (unset),
   LANG = "en_CA.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
   LANGUAGE = (unset),
   LC_ALL = (unset),
   LANG = "en_CA.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
Starting MySQL database server: mysqld . . . . . . . . . . . . . . failed!
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.0 (--configure):
 subprocess post-installation script returned error exit status 1
Errors were encountered while processing:
 mysql-server-5.0
E: Sub-process /usr/bin/dpkg returned an error code (1)
mail ~: 

I meant starting it without using the init script so that you get the full debugging output on your terminal instead of redirected to log file or /dev/null (whatever the case may be).

dpkg: error processing mysql-server-5.0 (--configure):
 subprocess post-installation script returned error exit status 1
Errors were encountered while processing:
 mysql-server-5.0
E: Sub-process /usr/bin/dpkg returned an error code (1)

Looks like mysql-server isn't fully installed yet. You could try letting apt fix it, e.g. apt-get -f install (with no packages), or alternatively configure locales for your server (the probable cause of installation of mysql-server failing):

locale -a  (show current installed locales)
dpkg-reconfigure locales

Thanks for all the help but I caved and just reinstalled the system after a quick data backup. Was not worth the hassle.