Yes, of course you can search for a character by its previous name(s). The time it will take for this redirect to stop working might be connected to the time it takes for the old name to be available again which can't be determined even by CipSoft. See related FAQ below:
Unfortunately, names of deleted or renamed characters are not immediately available for use by other characters due to technical limitations.
There are many factors which determine how much time must have passed before the name of a deleted character can be used again. Note, however, that it can take several months or even years before such names are available again, so we recommend you choose a different name for your character.
—FAQ: Name of Deleted/Renamed Character Wanted
Another similar FAQ, with basically the same answer, is this: Error Message: "This name is already used." Even Though no Such Character Exists. I've seen this myself, I was trying to create character Hunter of Dragons for weeks, every time I got that error message till one day it worked. However, I don't know what happened to the original (or previous) Hunter of Dragons. Perhaps he was deleted, not renamed as described in your question. In case he was renamed, it would mean the time period that searches using an old name redirects to the current character name is actually smaller than the time you have to wait till the old name becomes available. Anyway, this is the best answer I can give you.
Edit: With the help of Sir Dzidek, admin of GuildStats, we found a character that had been renamed in January: Sonekao Marrom. I was checking its page every single day since then. Today, its old name, Gruby Pucio, is no longer listed as a Former Name and when using a direct link to its page (or when searching for it), it does not redirect us to the new name anymore. This character was renamed in January 25, exactly 180 days ago. This confirms an old name is listed as a Former Name for 6 months. As previously stated, the duration an old name redirects to the new name as well as the duration a name is unavailable may be higher than that.