Security of Deterministic Encryption Scheme
You might be limiting yourself at the wrong aspect there.

Your goal is the ability to search on ciphertext; and you just look at deterministic encryption in your set of tools.

In order to use DE securely, the messagespace HAS TO contain enough entropy in order to protect from brute-force search. The only way to solve this is adding entropy at random either in the encryption process and/or the message (e.g. extend message by a couple of random bits at the start).

But what you actually want is "Searchable Encryption", google scholar will help you out. For example Abdalla et al. published "Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions" and Boneh et al. published "Public Key Encryption with Keyword Search". However, I don't know if there are any implementations of these schemes, and probably they are quite huge: PEKS based on IBE, which is based on pairings in elliptic curves.