It can be a limitation of MySQL.
Under the hood, Magento Search with MySQL search engine uses MySQL Full-Text Search. And out of the box, MySQL limits a length of a phrase being indexed to 3 symbols.
So, Magento doing its work well in this case (I believe this, but if not then it should be fixed), but MySQL actually just ignores a search string which is shorter than configuration value.
This limitation described in the MySQL documentation: "Fine-Tuning MySQL Full-Text Search" as well as the steps needed to customize this behavior: "Configuring Minimum and Maximum Word Length":
"The minimum and maximum lengths of words to be indexed are defined by the innodb_ft_min_token_size and innodb_ft_max_token_size for InnoDB search indexes, and ft_min_word_len and ft_max_word_len for MyISAM ones."
But take into account the notice from MySQL on the top of that page:
"Full-text search is carefully tuned for effectiveness. Modifying the default behavior in most cases can actually decrease effectiveness. Do not alter the MySQL sources unless you know what you are doing."
Be careful with this change as it may decrease your site performance.