Yes, that is the only way, iterate until you find a key which fits into 154 bits (address less than 03ffffffffffffffffffffffffffffffffffffff). That means it has to start with 0x00, 0x01, 0x02 or 0x03.
Some of the libraries support that already, otherwise as mentioned above, using a vanity address generator should be able to generate one.
(Vanity addresses are where you define the criteria how the resulting address should look like and usually they do a bruteforce search until such an address is found.)
In Javascript, ethereumjs-wallet and ethereumjs-icap can be used to achieve that. Or as a commandline tool, helpeth:
$ helpeth keyGenerate raw true
Address: 0x0008790cf214419f622db6484f07f73c19b4f546
Address (checksum): 0x0008790cf214419F622dB6484f07F73c19b4F546
ICAP: XE52 50DK T7BM 161X 0KHH RZXW FM60 K243 Q
Public key: 0xb146e3092d4177819f52038d26deb203d95c6e18f6c71812b68eafb0db4496366a093607d8e705bd688dedfa68dec9112e0baff256943c90cd221f04565f15eb
Private key: 0x413d8a0009d47eca4522d815b961d255a7aaad775bdefb1de29686a372aaa7c4
0x00,0x01,0x02or0x03and fit into the required 154 bits - which would reduce your search by a factor of 4. – jimkberry Mar 07 '16 at 17:05