Thanks to netcrash from the symfony irc channel I came along regular expressions in MySQL: http://dev.mysql.com/doc/refman/4.1/en/regexp.html

Tutorial: http://www.brainbell.com/tutorials/MySQL/Using_MySQL_Regular_Expressions.htm

I'm using it to select all entries that don't start with a letter in an alphabetical pagination:

$c = new Criteria();
$regex = CmsUserPeer :: USERNAME." NOT REGEXP '^[[:alpha:]]'";
$c->add(CmsUserPeer :: USERNAME, $regex, Criteria::CUSTOM);
$this->cms_user = CmsUserPeer :: doSelect($c);

Instead of selecting by REGEXP pookey had the idea of "using substr to get the first char, then getting it's character code, and doing a BETWEEN on it" for performance reasons.

There is another faster solution:

$c = new Criteria();
$cq = "substring( ".CmsUserPeer :: USERNAME.", 1, 1 ) NOT BETWEEN  'a' AND  'z'";
$c->add(CmsUserPeer :: USERNAME, $cq, Criteria::CUSTOM);
$this->cms_user = CmsUserPeer :: doSelect($c);