htmlentities does work with utf-8 if that's supplied as third argument, and utf-8 does include greek characters. Your problem lies elsewhere. Also, I'd run the string through mysql_real_escape_string at the very last, to avoid the risk that some other function would introduce a character used as delimiter in your database.
# Test string using greek letters
$s = "Δεν βρέθηκαν αποτελέσματα.";
echo 'Initial string: ' . $s . "<br/>\n";
$s = strip_tags(trim($s));
$s = htmlentities($s, ENT_QUOTES, 'utf-8');
echo 'Html entities: ' . $s."<br/>\n";
# Use mysql_real_escape string just before inserting to or updating database, to avoid
# introducing characters that screw up your sql statement. And only do so if you actually insert
# it do the database
$db_escaped = mysql_real_escape_string($s);
echo 'Escaped for DB: ' . $db_escaped; # same as above line for my particular DB.
HTML code Output
Initial string: Δεν βρέθηκαν αποτελέσματα.<br/>
Html entities: Δεν βρέθηκαν αποτελέσματα.<br/>
Escaped for DB: Δεν βρέθηκαν αποτελέσματα.
Rendered output
Initial string: Δεν βρέθηκαν αποτελέσματα.
Html entities: Δεν βρέθηκαν αποτελέσματα.
Escaped for DB: Δεν βρέθηκαν αποτελέσματα.